10.1.二叉搜索树

发表于 更新于 分类于 ， 阅读次数： 本文字数： 670 阅读时长 ≈ 2 分钟

\(10.1\)二叉搜索树

1.\(BST\)相关概念

  • The tree is made up of \(nodes\) that contain \(links\) that are either \(null\) or references to other nodes.
  • Every node is pointed to by just one other node, which is called its \(parent\) (except for one node, the \(root\), which has no nodes pointing to it).
  • Each node has exactly two links, which are called its \(left\) and \(right\) links, that point to nodes called its \(left child\) and \(right child\).
  • we can define a binary tree as a either a null link or a node with a left link and a right link, each references to (disjoint) subtrees that are themselves \(binary trees\). In a binary search tree, each node also has a key and a value, with an ordering restriction to support efficient search

  \(BST\)也遵循如下的性质：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
private class BST<Key> {
    private Key key;
    private BST left;
    private BST right;

    public BST(Key key, BST lf, BST rt) {
        this.key = key;
        this.left = lf;
        this.right = rt;
    }

    public BST(Key key) {
        this.key = key;
    }
}

2.\(BST\)操作

  \(a.\)find

1
2
3
4
5
6
7
8
9
10
11
12
static BST find(BST T, Key sk) {
    if (T == null) {
        return null;
    }
    if (sk.equals(T.key)) {
        return T;
    } else if (sk < T.key) {
        return find(T.left, sk);
    } else {
        return find(T.right, sk);
    }
}

  \(b.\)insert

  我们永远只插入左节点！ 

1
2
3
4
5
6
7
8
9
10
11
static BST insert(BST T, Key sk) {
    if (T == null) {
        return new BST(sk);
    }
    if (sk < T.key) {
        T.left = insert(T.left, sk);
    } else if (sk > T.key) {
        T.right = insert(T.right, sk);
    }
    return T;
}

  \(c.\)delete

  我们可以通过将一个节点替代为它的后继节点，来实现该节点的删除。一个节点的后继节点(\(successor\))是它右子树的最小节点。我们可以通过以下步骤实现delete：

  1. 保存待删除节点(\(x\))的链接(\(link\))。
  2. 让\(x\)指向后继节点(\(y\))。
  3. 将\(x\)的右链接指向deleteMin(t.right)，其中deleteMin会返回指向右子树的链接，而右子树中所有元素都大于(\(x\))。
  4. 让后继节点的左链接指向\(x\)的左子树。

  下面是该过程的图示：

  下面我们分部实现delete操作。

  \(i.\)deleteMin

  我们可以通过如下方式递归实现deleteMin：

  1. 找到最小的节点，然后返回它的父亲的右儿子(把指向它的链接给忽略掉了，这样就相当于删掉这个元素了)。
  2. 把父节点的左链接指向返回的节点。
  3. 更新子树的大小。 
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    public void deleteMin() {
        root = deleteMin(root);
    }

    private void deleteMin(Node p) {
        if (p.left == null) {
            return p.right;
        }

        p.left = deleteMin(p.left);
        p.size = p.left.size + p.right.size + 1;
        return p;
    }
  \(ii.\)最小节点
1
2
3
4
5
6
private Node min(Node p) {
    if (p.left == null) {
        return p;
    }
    return min(p.left);
}
  \(iii\)delete操作
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
public void delete(Key key) {
    root = delete(root, key);
}

private Node delete(Node p, Key key) {
    if (p == null) {
        return null;
    }

    int cmp = key.compareTo(p.key);
    if (cmp > 0) {
        p.right = delete(p.right, key);
    } else if (cmp < 0) {
        p.left = delete(p.left, key);
    } else {
        // solve the one-node condition.
        if (p.right == null) return p.left;
        if (p.left == null) return p.right;

        //store the to-delete node, so that we can connect its subtree.
        Node t = p;
        p = min(t.right);
        p.right = deleteMin(t.right);
        p.left = t.left;
    }
    p.size = p.left.size + p.right.size + 1;
    return p;
}