How does the search operation for a red-black tree work and how does it take $O(\log n)$ time, where $n$ is the number of items? I know a red-black tree takes $O(\log n)$ recolorings and $O(1)$ rotations, but I was specifically interested in a good description of its search operation.
$\begingroup$
$\endgroup$
1
-
1$\begingroup$ If you're wondering how red-black trees manage $O(\log n)$ depth, you might want to look into 2-3-4 trees. Red-black trees are 2-3-4 trees in disguise. $\endgroup$– Pseudonym ♦Commented Sep 30, 2014 at 5:04
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
The search operation is the same for all binary search trees - recurse into the left or right branch depending on whether the element is smaller or larger than the current root. Red-black trees are not special.
The complexity of the search operation is equal to the height of the tree.
Different varieties of binary search trees differ in what guarantees on height of the tree they give, and in how exactly they maintain these guarantees. Red-black trees and AVL trees give you guaranteed O(log n) height, which is why search is O(log n).
