in Algorithms recategorized by
1,641 views
0 votes
0 votes

Red-black trees are one of many search tree schemes that are “balanced” in order to guarantee that basic dynamic-set operations take _____ time in the worst case.

  1. $O(1)$
  2. $O( \lg n)$
  3. $O(n)$
  4. $O(n \lg n)$
in Algorithms recategorized by
1.6k views

1 comment

log n time to search,delete
0
0

4 Answers

2 votes
2 votes
Best answer

option 2

Red-black trees are one of many search-tree schemes that are "balance" in order to guarantee that basic dynamic-set operations take O(lg n) time in the worst case.

A red-black tree with n internal nodes has height at most 21g(n + 1).

Proof We first show that the subtree rooted at any node x contains at least 2bh(x) -1 internal nodes. We prove this claim by induction on the height of x. If the height of x is 0, then x must be a leaf (NIL), and the subtree rooted at x indeed contains at least 2bh(x)-1 = 2- 1 = 0 internal nodes. For the inductive step, consider a node x that has positive height and is an internal node with two children. Each child has a black-height of either bh(x) or bh(x) - 1, depending on whether its color is red or black, respectively. Since the height of a child of x is less than the height of x itself, we can apply the inductive hypothesis to conclude that each child has at least 2bh(x) -1 -1 internal nodes. Thus, the subtree rooted at x contains at least (2bh(x)-1 -1) + (2bh(x)-1 -1) + 1 = 2bh(x)- 1 internal nodes, which proves the claim.

To complete the proof of the lemma, let h be the height of the tree. According to property 3, at least half the nodes on any simple path from the root to a leaf, not including the root, must be black. Consequently, the black-height of the root must be at least h/2; thus,

n 

2h/2 - 1.

Moving the 1 to the left-hand side and taking logarithms on both sides yields lg (n + 1)  h/2, or h  21g (n + 1).

An immediate consequence of this lemma is that the dynamic-set operations SEARCH, MINIMUM, MAXIMUM, SUCCESSOR, and PREDECESSOR can be implemented in O(lg n) time on red-black trees, since they can be made to run in O(h) time on a search tree of height h and any red-black tree on n nodes is a search tree with height O(lg n).

source:coreman

selected by
0 votes
0 votes
option B) $O(lg n)$

Red-Black trees are always 'balanced' means at any moment both the left and right subtrees will be nearly of the same height (maximum difference between heights is 1).

Search: The worst case is when node being searched is a leaf node. This takes lg n time which is the height of the tree.

Insert: The worst case happens when every node from root to the leaf has to be balanced which can be done in lg n time.

Delete: The worst case happens when every node from the node to root has to be balanced which can be done in lg n time.

So the worst case is time is $O(lgn)$
edited by

4 Comments

how????
0
0
–1
–1
@ venkat

see one thing, U r answering, its fine but u know along with it if u could answer in some informative way so that other people can also take help from it...
1
1
@venkat_sirvisetti, Can you please support your answer with an Example?Say?
0
0
0 votes
0 votes

ans O(log n)

this question is already answered check this link

https://gateoverflow.in/113819/ugcnet-dec2016-iii-33

0 votes
0 votes
  • in balance tree dynamic–set operations ( Search, Insert, and Remove operations) will take O(logn) time .example avl tree, red black tree

so option b is right

Answer:

Related questions