algorithmdata-structuresbinary-search-treered-black-treetree-balancing

Does a Red-Black Tree modify the left-to-right order of its leaves when it re-balances itself?


In other words, If you were to read the values of the leaves in a red black tree from left-to-right immediately after an insertion, would that order remain the same after performing balancing operations on the tree?


Solution

  • Re-balancing may make a sibling of a node its new parent, but it can not change the relative order. Keep in mind that the red-black tree is a binary search tree and thus it should keep elements smaller than a given element in its left subtree and elements greater than it in its right subtree. Swapping the children of a vertex will reverse the inequality.