You are not logged in. Please login at www.codechef.com to post your questions!

×

Data Structure

Any idea of how to implement a Data Structure that supports two operation in less than O(n) and the ds is sorted?
Insert
Delete

asked 07 Mar '18, 22:51

phantomhive's gravatar image

4★phantomhive
944
accept rate: 0%

BST(Binary Search Tree)
Insertion and Deletion Complexity: O(log2(n))

(07 Mar '18, 23:05) shawnfrost5★

@shawnfrost in bst its O(h) and worst case the insertion and deletion is O(n) anything better than that?

(07 Mar '18, 23:08) phantomhive4★

AVL Tree.
They are same as BST but are height balanced.
So, h remain log2(n) always.

(07 Mar '18, 23:15) shawnfrost5★

how to delete in avl trees? and also like is there a way if i can find nth max in avl tree?

(07 Mar '18, 23:19) phantomhive4★

Complete implementation is available on geeksforgeeks.
Consider maintaining count of nodes on the left and right of each node.
Now,perform binary search skipping all nodes before nth node.
O(log2(n)) per query.

(07 Mar '18, 23:26) shawnfrost5★

thanks !!!

(07 Mar '18, 23:29) phantomhive4★
showing 5 of 6 show all
toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×1,391

question asked: 07 Mar '18, 22:51

question was seen: 185 times

last updated: 07 Mar '18, 23:29