CODEWITHSUNDEEP
javatreered-black-tree
Joey Franklin
Joey Franklin

Reputation: 6833

Do red-black trees have to be in sorted order?

I have a pretty simple question here: Do red-black trees have to be in sorted order? I ask this because the small box on the right side of the wikipedia page (http://en.wikipedia.org/wiki/Red–black_tree) says that search time is O(log(n)); however, wouldn't this only be true if the tree was sorted. On the other hand though, the properties s

Upvotes: 2

Views: 1657

Answers (4)

Joe K
Joe K

Reputation: 18424

The whole point of a red-black tree is to keep the tree balanced to some degree. If you relax the sorting constraint, then keeping a tree balanced is trivial since you can put nodes wherever you want.

Upvotes: 1

Brian
Brian

Reputation: 17309

Red black trees are sorted trees (the whole all RB trees are sorted binary trees, but not all sorted binary trees are red black trees thing). The difference between a plain binary tree and a red black tree is that RB trees guarantee that search time will be log2(n) because they're balanced. In essence, it guarantees that the number of layers for n nodes will never be more than log2(n), keeping the binary search in check.

A plain binary tree with no balancing will not always produce a log2(n) time complexity. For example, if I have a tree like this:

  4
 / \
3   6
     \
      7
       \
       10
         \
         12

For this unbalanced tree, the actual search time is nearly linear to find 12 (worst-case time complexity, 5 comparisons). For a balanced tree which has at most log2(n) layers, the tree above could be:

     7
   /   \
  4    10
 / \     \
3   6    12

And so finding any of the lowest-layer nodes will take at most 3 comparisons (which fits log2(n) since it's actually rounded up, ceil[log2(6)] = 3)

The key here is to remember that the number of layers is functionally equivalent to the number of comparisons you have to make when you start at the root. Red-black trees limit the number of layers to a bare minimum via balancing, while vanilla, unbalanced binary trees don't.

Upvotes: 6

Tim Bender
Tim Bender

Reputation: 20442

A red-black tree is a binary search tree. By definition of a binary search tree, the left child (and all descendants) must be less than the parent and the right child (and all descendants) must be greater than the parent. Thus there is an ordering.

Upvotes: 2

gtgaxiola
gtgaxiola

Reputation: 9331

Red-Black Trees have a search time of O(log n) due to its way of setting up their nodes with a natural order.

When you do a node comparison you theoretically discard half of the options when you take on a branch.

Since you can only "half" log n times before you get to one element, then your search complexity is O(log n)

Upvotes: 1

Related Questions