Dark Mode

1,717 views

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

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

2* ^{h/}*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

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

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

1