Skip to main content
Computer Science

Return to Question

Tweeted twitter.com/#!/StackCompSci/status/519020732677124096
edited tags
Link
Raphael
Raphael
  • 72.9k
  • 30
  • 181
  • 393
added 10 characters in body; edited title
Source Link
Juho
Juho
  • 22.8k
  • 7
  • 62
  • 117

Red-black trees How can one search in O(lognlog n). How time in a red-black tree?

I was curious to see howHow does the 'search' operationsearch operation for a red-black tree exactly workswork and how does it take O(logn)$O(\log n)$ time, where $n$ is the number of items? I know a red-black tree takes O(logn)$O(\log n)$ recolorings and O(1)$O(1)$ rotations, but I was specifically interested in a good description of its search operation.

Thank you!

Red-black trees O(logn). How?

I was curious to see how the 'search' operation for a red-black tree exactly works and how does it take O(logn)? I know a red-black tree takes O(logn) recolorings and O(1) rotations, but I was specifically interested in a good description of its search operation.

Thank you!

How can one search in O(log n) time in a red-black tree?

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.

Source Link
user21996
user21996
  • 101
  • 2
  • 7

Red-black trees O(logn). How?

I was curious to see how the 'search' operation for a red-black tree exactly works and how does it take O(logn)? I know a red-black tree takes O(logn) recolorings and O(1) rotations, but I was specifically interested in a good description of its search operation.

Thank you!