recategorized by
2,285 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)$
recategorized by

4 Answers

Best answer
2 votes
2 votes

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
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

0 votes
0 votes
5 answers
1
go_editor asked Mar 24, 2020
3,452 views
The minimum number of scalar multiplication required, for parenthesization of a matrix-chain product whose sequence of dimensions for four matrices is $< 5,10,3,12,5 $ is...
0 votes
0 votes
4 answers
2
go_editor asked Mar 24, 2020
2,096 views
Dijkstra’s algorithm is based onDivide and conquer paradigmDynamic programmingGreedy approachBacktracking paradigm
0 votes
0 votes
6 answers
3
go_editor asked Mar 24, 2020
1,502 views
Match the following with respect to algorithm paradigms :$\begin{array}{clcl} & \textbf{List-I} & {} & \textbf{List-II} \\ \text{a.} & \text{Merge sort} & \text{i.} & \te...
2 votes
2 votes
7 answers
4
go_editor asked Jan 31, 2017
7,512 views
Any decision tree that sorts n elements has height ____$\Omega (\lg \: n)$$\Omega (n)$$\Omega (n \: \lg \: n)$$\Omega (n^2)$