algorithm - 赤黒木は、バランスを取り直すときに葉の左から右への順序を変更しますか?

Question

つまり、挿入直後に赤黒の木の葉の値を左から右に読み取った場合、その順序は木でバランシング操作を実行した後も同じままでしょうか?

Answer 1

バランスを再調整すると、ノードの兄弟が新しい親になる場合がありますが、相対的な順序を変更することはできません。赤黒木は二分探索木であるため、指定された要素よりも小さい要素を左側の部分木に保持し、それよりも大きい要素を右側の部分木に保持する必要があることに注意してください。頂点の子を交換すると、不等式が逆転します。