10.1.二叉搜索树

\(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;
}