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 | private class BST<Key> { |
2.\(BST\)操作
\(a.\)find
1 | static BST find(BST T, Key sk) { |
\(b.\)insert
我们永远只插入左节点! 1
2
3
4
5
6
7
8
9
10
11static 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
:
- 保存待删除节点(\(x\))的链接(\(link\))。
- 让\(x\)指向后继节点(\(y\))。
- 将\(x\)的右链接指向
deleteMin(t.right)
,其中deleteMin
会返回指向右子树的链接,而右子树中所有元素都大于(\(x\))。 - 让后继节点的左链接指向\(x\)的左子树。
下面是该过程的图示:
下面我们分部实现delete
操作。
\(i.\)deleteMin
我们可以通过如下方式递归实现deleteMin
:
- 找到最小的节点,然后返回它的父亲的右儿子(把指向它的链接给忽略掉了,这样就相当于删掉这个元素了)。
- 把父节点的左链接指向返回的节点。
- 更新子树的大小。
1
2
3
4
5
6
7
8
9
10
11
12
13public 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 | private Node min(Node p) { |
\(iii\)delete
操作
1 | public void delete(Key key) { |