BST-dən silmək əlavə etməkdən çətindir: silinən düyünün alt ağacları var və xassə (sol < düyün < sağ) qorunmalıdır. Hər şey silinən düyünün uşaqlarının sayından asılıdır. Əlavə və axtarış üçün əvvəlki mövzuya baxın.

Silmənin üç halı: yarpaq, bir uşaq, iki uşaq
Silmənin üç halı: yarpaq, bir uşaq, iki uşaq

Üç hal

  1. Yarpaq (uşaq yoxdur): sadəcə çıxarırıq: valideynin göstəricisi None olur.
  2. Bir uşaq: düyünü çıxarıb yerinə uşağı qoyuruq (valideyn düyünü yox, onun uşağına işarə edir). Uşağın alt ağacı xassəni pozmur, çünki o artıq silinən düyünün alt ağacı idi.
  3. İki uşaq: düyünü çıxara bilmərik, çünki iki alt ağacı bir yerə bağlamaq lazımdır. Əvəzinə düyünün açarını varisin (successor) açarı ilə əvəz edir, sonra varisi silirik. Varis, sağ alt ağacın ən kiçik düyünüdür. Onun sol uşağı olmur, deməli onu silmək 1-ci və ya 2-ci haldır.

Varis seçilməsi xassəni saxlayır: o, sol alt ağacdakıların hamısından böyük və sağ alt ağacın qalanından kiçikdir. Simmetrik seçim: sələf (predecessor), sol alt ağacın ən böyüyü.

Reallaşdırma

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

def insert(node, key):
    if node is None:
        return Node(key)
    if key < node.key:
        node.left = insert(node.left, key)
    elif key > node.key:
        node.right = insert(node.right, key)
    return node

def build(keys):
    root = None
    for k in keys:
        root = insert(root, k)
    return root