Operationer på binära sökträd

Ett binärt sökträd (BST) använder en ordningsregel i varje delträd: mindre nycklar ligger till vänster och större till höger. Här antar vi unika heltalsnycklar. I riktiga system behöver man också välja en tydlig policy för dubbletter och jämförelser.

Sökning och insättning

Jämför målet med nodens nyckel. Vid träff avslutas sökningen. Annars går vi åt vänster eller höger tills nyckeln hittas eller en tom position nås. Insättning följer samma väg men skapar en nod där barnet saknas. Korrektheten bygger på att ordningsregeln gäller för hela delträdet, inte bara närmaste barnen.

C#

C# | BST.cs

public sealed class Node
{
    public int Key;
    public Node? Left, Right;
    public Node(int key) => Key = key;
}

static bool Contains(Node? root, int key)
{
    while (root is not null)
    {
        if (key == root.Key) return true;
        root = key < root.Key ? root.Left : root.Right;
    }
    return false;
}

static Node Insert(Node? root, int key)
{
    if (root is null) return new Node(key);
    if (key < root.Key) root.Left = Insert(root.Left, key);
    else if (key > root.Key) root.Right = Insert(root.Right, key);
    return root; // duplicates ignored
}

C++

C++ | BST.cpp

#include <memory>
struct Node {
    int key;
    std::unique_ptr<Node> left, right;
    explicit Node(int k) : key(k) {}
};

bool contains(const Node* root, int key) {
    while (root) {
        if (root->key == key) return true;
        root = key < root->key ? root->left.get() : root->right.get();
    }
    return false;
}

void insert(std::unique_ptr<Node>& root, int key) {
    if (!root) { root = std::make_unique<Node>(key); return; }
    if (key < root->key) insert(root->left, key);
    else if (key > root->key) insert(root->right, key);
    // duplicate keys are ignored
}

Borttagning har tre fall

1. Löv: ta bort noden.
2. Ett barn: ersätt noden med barnet.
3. Två barn: ersätt nyckeln med inorder-efterföljaren, det minsta värdet i höger delträd, och ta sedan bort efterföljaren från sin ursprungliga position. Föregångaren från vänster delträd fungerar också.

Att bara koppla loss en nod med två barn kan förlora ett helt delträd. C++ kräver extra försiktighet med pekare och ägarskap. Även C#-kod kan påverkas om andra delar håller referenser till noder.

Kod för borttagning

Följande implementationer återanvänder Node från exemplet med insättning. I C# behöver du tilldela det returnerade rotvärdet eftersom roten kan bytas ut. I C++ uppdaterar std::unique_ptr<Node>& ägarskapet säkert. Spara inte pekare till noder som kan tas bort.

C#

C# | BSTDeletion.cs

// Call: root = Remove(root, key); the root may change.
static Node? Remove(Node? root, int key)
{
    if (root is null) return null;
    if (key < root.Key) root.Left = Remove(root.Left, key);
    else if (key > root.Key) root.Right = Remove(root.Right, key);
    else
    {
        if (root.Left is null) return root.Right;
        if (root.Right is null) return root.Left;
        Node successor = root.Right;
        while (successor.Left is not null) successor = successor.Left;
        root.Key = successor.Key;
        root.Right = Remove(root.Right, successor.Key);
    }
    return root;
}

C++

C++ | BSTDeletion.cpp

#include <memory>
// Uses the Node type declared in the insertion example above.
void erase(std::unique_ptr<Node>& root, int key) {
    if (!root) return;
    if (key < root->key) erase(root->left, key);
    else if (key > root->key) erase(root->right, key);
    else {
        if (!root->left) { root = std::move(root->right); return; }
        if (!root->right) { root = std::move(root->left); return; }
        Node* successor = root->right.get();
        while (successor->left) successor = successor->left.get();
        root->key = successor->key;
        erase(root->right, successor->key);
    }
}

Kostnad och höjd

Sökning, insättning och borttagning följer en rot-till-löv-väg och tar O(h) tid vid höjd h. Ett balanserat träd ger O(log n), men sorterad insättning i ett naivt BST kan skapa en kedja med O(n). Rekursiv kod använder O(h) stackminne; iterativ uppslagning kan använda O(1) extra minne.

Övning: Sätt in 8, 3, 10, 1, 6, 14, 4, 7, sök efter 7 och ta sedan bort 3. Kontrollera att inorder-traversering fortfarande ger sorterad ordning.

Referens: W3Schools binära sökträd.