1

I've been playing with a RBT visualizer and don't understand how the following is considered height-balanced. The wikipedia article claims that if the RBT properties are satisfied, then the height of the farthest leaf is no greater than twice the height of height of the closest leaf. From my understanding, the below would violate this property, even if the RBT properties are satisfied (the depth of 1 is 1 and the depth of 6 is 3). Where is my logic flawed here? enter image description here

ilikemath3.14
  • 39
  • 6

1 Answers1

1

From the Wikipedia article:

The leaf nodes of red–black trees ( NIL  in figure 1) do not contain keys or data. These "leaves" need not be explicit individuals in computer memory: a NULL pointer can —as in all binary tree data structures— encode the fact that there is no child node at this position in the (parent) node. Nevertheless, by their position in the tree, these objects are in relation to other nodes…

The diagram you've included in your question has omitted these NIL nodes, but they are relevant for the determination of balanced. Using the rule you describe ("the path from the root to the farthest leaf is no more than twice as long as the path from the root to the nearest leaf"), the path from the root to the nearest leaf has a distance of two (not one), and the path from the root to the farthest leaf has a distance of four (not three).

Since four is not more than twice two, this tree complies with the "balanced" rule.

Peter Duniho
  • 68,759
  • 7
  • 102
  • 136
  • Thanks - I do believe there is some confusion here, given that AVL tree NIL nodes are considered to have a height of -1, so when calculating the height of a leaf, it is always 0. It seems that with RBTs, the height of a leaf is always 1, which differs from the AVL tree. Would you concur with this explanation? – ilikemath3.14 May 07 '21 at 23:37
  • I would have to review more closely, but IIRC AVL trees don't care about depth/height of nodes per se at all, nor are empty child nodes (NIL) treated differently. AVL trees focus on left/right balance, assigning a balance factor of -1, 0, or 1 to each node depending on the relative number of descendants to either side (left or right). That said, as a general rule you would be correct to observe that you cannot necessarily take the terminology from one particular abstract data structure concept, and reuse the exact same terminology in another. There always may be subtle differences. – Peter Duniho May 07 '21 at 23:59
  • Yes you are somewhat recalling correctly, but not exactly... it really depends on the relative height, which is similar, but different than the number of nodes. Thanks for the feedback! – ilikemath3.14 May 08 '21 at 00:11