AVL ve red-black: Dengeyi korumak

AVL her düğümde sol/sağ height farkını en fazla1 tutar. Ekleme sonrası etkilenen ataları yukarı doğru günceller, LL/RR durumunda tek, LR/RL durumunda çift rotation yapar. Rotation inorder anahtar sırasını değiştirmez; yalnız yükseklik ve bağlantıları düzenler. Silme birden çok atada dengeleme gerektirebilir.

Red-black renk kurallarıyla height'i sınırlar: root siyah, kırmızı düğümün kırmızı çocuğu yok, her düğümden NIL yapraklara siyah sayısı eşit. Bu kurallar height≤2log₂(n+1) sonucunu destekler. NIL kavramı eksik çocukların matematiksel yaprağıdır; uygulama sentinelle veya null kontrolüyle temsil edebilir.

AVL daha sıkı denge sunar; red-black daha gevşek dengeyle güncelleme dinamiklerinde farklı sabit maliyetler verir. “Biri her durumda daha hızlı” denemez. Kütüphane kullanırken kendin yanlış rotation kodu yazmak yerine sözleşme testlerine odaklan; eğitim implementasyonunda parent/root bağlantıları ve augmented alanları unutma.

# Right rotation in tuple form: (key, left, right).
def rotate_right(y):
    ykey, x, right = y
    if x is None: raise ValueError("missing pivot")
    xkey, left, middle = x
    return (xkey, left, (ykey, middle, right))
assert rotate_right((30,(20,(10,None,None),None),None))[0] == 20