Binary tree, BST ve sıra istatistikleri

Binary tree her düğüme en fazla iki çocuk verir; BST bunun üstüne bir arama düzeni ekler. Sol alt ağaç küçük, sağ büyük anahtarlardan oluşur; tekrarların nasıl tutulacağı sözleşmedir. Sadece doğrudan çocukları kontrol etmek bütün BST invariant'ını doğrulamaz: derindeki düğüm üst atanın sınırını da sağlamalıdır.

Arama root'tan bir yola iner; maliyet height h'ye bağlıdır. Sıralı ekleme ağacı zincire çevirebilir ve h=n olur. Inorder traversal BST'de anahtarları sıralı verir. Silme yapraktan kolaydır; tek çocukta bağlantı geçer, iki çocukta successor/predecessor ile değişim ve asıl düğümün silinmesi gerekir.

Subtree size alanı ekleyerek rank ve select işlemleri yapılabilir. Her rotation/ekleme/silmede bu metadata güncellenmelidir. Augmentation sadece alan eklemek değil, güncelleme invariant'ını korumaktır. Denge olmadan sıra istatistiği de O(n)'e düşebilir.

def valid_bst(node, lo=float("-inf"), hi=float("inf")):
    if node is None: return True
    key, left, right = node
    return (lo < key < hi and valid_bst(left, lo, key)
            and valid_bst(right, key, hi))
assert not valid_bst((10,(5,None,(12,None,None)),None))