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.

  • 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 Sep 30 '14 at 5:04

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.