Qırmızı-qara ağaclar

AVL ağacları sərt balans saxlayır və buna görə tez-tez fırlanır. Qırmızı-qara ağac şərti yumşaldır: hər düyün rəng alır, rənglər haqqında bir neçə qayda isə ən uzun yolun ən qısadan ən çox iki dəfə uzun olmasını təmin edir. Onda hündürlük 2 · log2(n+1)-dən çox olmur, əlavə və silmə isə çox az fırlanma tələb edir.

Beş qayda

1. Hər düyün qırmızı və ya qaradır.
2. Kök qaradır.
3. Boş yarpaqlar (None) qara sayılır.
4. Qırmızı düyünün uşaqları yalnız qaradır: iki qırmızı yan-yana olmur.
5. İstənilən düyündən yarpaqlara gedən bütün yollarda qara düyünlərin sayı eynidir (qara hündürlük).

Bu hündürlüyü nə üçün məhdudlaşdırır? Ən qısa yol yalnız qara düyünlərdən ibarətdir, ən uzun yol qara və qırmızını növbələşdirir (4-cü qayda), 5-ci qaydaya görə isə hər ikisində qara sayı eynidir. Deməli hündürlük 2 · bh-dən çox deyil, qara hündürlüyü bh olan ağacda isə ən azı 2^bh - 1 düyün var. Buradan h ≤ 2 · log2(n+1).

Qaydaları kodda yoxlamaq

RED, BLACK = "R", "B"

class Node:
    def __init__(self, key, color, left=None, right=None):
        self.key = key
        self.color = color
        self.left = left
        self.right = right

def is_red(n):
    return n is not None and n.color == RED