1、概要
这里主要讲解二叉搜索树的设计及实现。
代码地址: github地址
https://github.com/fofcn/operation-system/blob/main/%E5%AE%9E%E8%B7%B5/os/src/main/java/lang/tree/BinarySearchTree.java
2、概念
二叉搜索树是用一颗二叉树来组织的，这棵树可以使用一个链表来表示，每个节点都是一个对象。
2.1、节点
每个节点都有一个父节点、左孩子和右孩子。
2.2、性质
假设x是二叉搜索树的一个节点。
如果y是x的左子树的一个节点，那么y.key<=x.key。
如果y是x的右子树的一个节点，那么y.key>=x.key。
3、操作
搜索树支持很多动态集合操作，包括SEARCH、MINIMUM、MAXIMUM、FLOOL、CELL、INSERT和DELETE等。我们主要讲解查找、插入和删除三类主要的操作。
3.1、插入
二叉搜索树的插入相对比较简单，需要在二叉搜索树上查找插入的位置，然后新建接节点插入，然后修改该节点的父级节点属性。
例如：将 10 16 4 1 12 2 0 11 18 6 分别插入到二叉搜索树中，会得到如下图所示的二叉搜索树
Java实现代码如下：
private void putInternal(Key key, Value value) {
// 初始化二叉搜索树
if (root == null) {
root = new Node(key, value);
size.incrementAndGet();
} else {
// 从根节点开始查找插入位置
Node tmp = root;
while (tmp != null) {
int cmp = key.compareTo(tmp.key);
// 如果待插入节点比当前节点小，那么查看该节点的左孩子是否为空，如果为空，则将待插入节点插入到左孩子
if (cmp < 0) {
if (tmp.left == null) {
tmp.left = new Node(key, value);
tmp.left.parent = tmp;
size.incrementAndGet();
break;
}
tmp = tmp.left;
// 如果待插入节点比当前节点小，那么查看该节点的右孩子是否为空，如果为空，则将待插入节点插入到右孩子
} else if (cmp > 0) {
if (tmp.right == null) {
tmp.right = new Node(key, value);
tmp.right.parent = tmp;
size.incrementAndGet();
break;
}
tmp = tmp.right;
} else {
tmp.value = value;
break;
}
}
}
}3.2、查找
在一颗二叉搜索树中查找一个指定关键字。
在二叉搜索树中查找一个指定关键字从树根开始查找，并沿着这棵树的一条路径向下进行查找。
例如：如果在上图中的二叉搜索树中查找节点为6的节点，那么搜索路径为10->4-6
Java实现代码如下：
/**
* 根据key查找Key对应的节点
* @param key 关键字
* @return key对应的关键字，null没有找到关键字对应的节点
*/
private Node getInternal(Key key) {
Node tmp = root;
int cmp;
// 遍历树查找节点
while (tmp != null && (cmp = key.compareTo(tmp.key)) != 0) {
if (cmp < 0 ) {
tmp = tmp.left;
} else {
tmp = tmp.right;
}
}
return tmp;
}3.3、删除
二叉搜索树的删除稍微有点复杂，根据二叉搜索树的特性，删除基本分为三种情况：
假设待删除节点为x：
-
如果x没有孩子节点，那么修改该孩子的父节点为null
如下图所示：将6节点删除时直接删除并更新节点4的右孩子为null
-
如果x只有一个孩子节点，那么将这个孩子提升到x位置，并修改x的父节点对应的左右孩子为这个孩子节点
如下图：将12节点的值删除时，需要将16节点的左孩子更新为11,11节点的父节点更新为16
删除后如下图所示
-
如果x有两个孩子节点，那么就需要在x的右子树中查找x的后继节点y，并将y提升到节点x的位置，并将x的左子树成为y的左子树，将替换y的右子树为x的右子树
如下图所示：如果删除4节点，则需要从4节点的右孩子中查找右孩子中最小的节点为5，将5提升到节点4的位置，更新5的父节点为10，更新5的左孩子为1，更新6的左孩子为null
删除后如下图所示：
Java代码实现如下：public void delete(Key key) { if (key == null) { throw new IllegalArgumentException(); } Node tmp = root; while (tmp != null) { int cmp = key.compareTo(tmp.key); if (cmp < 0) { tmp = tmp.left; } else if (cmp > 0) { tmp = tmp.right; } else { // 找到了待删除的节点 // 情况1：如果该节点既没有左孩子也没有右孩子，那么就直接删除 // 情况2：如果该节点只有一个孩子那么直接将该孩子提升到该孩子的位置上 // 情况3：如果该节点既有左孩子又有右孩子,则查找待删除节点的右孩子中最小的孩子，并将最小的孩子提升到待删除节点的位置 // 左孩子为空，那么用右孩子替换为tmp if (tmp.left == null) { transplant(tmp, tmp.right); } else if (tmp.right == null) { // 右孩子为空，那么用左孩子替换掉tmp transplant(tmp, tmp.left); } else { // 左右孩子都不为空 // 查找右孩子中最小的节点 Node min = min(tmp.right); // 右孩子中最小节点的父级节点不是tmp表示最小节点不是tmp的直接孩子 // 那么这种情况下，需要将最小节点的右孩子替换最小节点的位置 // 将最小节点的右孩子设置为tmp右孩子 // 将最小节点的右孩子的父设置为最小节点 if (min.parent != tmp) { transplant(min, min.right); min.right = tmp.right; min.right.parent = min; } // 用tmp右子树最小节点替换掉tmp // 最小节点的左孩子更新为tmp的左孩子 // 最小节点的左孩子的父节点更新为最小节点 transplant(tmp, min); min.left = tmp.left; min.left.parent = min; } tmp = null; break; } } }
private void transplant(Node del, Node child) {
// 更新待删除节点的父节点
if (del.parent == null) {
root = child;
} else if (del == del.parent.left) {
del.parent.left = child;
} else {
del.parent.right = child;
}
// 更新孩子节点的父节点为待删除节点的父节点
if (child != null) {
child.parent = del.parent;
}
}4 算法运行时间
| 假设一颗二叉搜索树的高度为h | 操作 | 时间 |
|---|---|---|
| 插入 | O(h) | |
| 查找 | O(h) | |
| 删除 | O(h) |
最好情况分析
最好情况就是二叉搜索树完全平衡，即二叉搜索树中的每个节点都有左右两个孩子，此时树的高度O(logn),如下图所示：
最坏情况分析
最坏情况是所有节点都是按照正序插入，那么此时树的高度是n,插入、查找和删除的时间是O(n)，如下图所示
平均情况分析
5、总结
- 二叉搜索树保证在O(n)的时间内完成插入、查找和删除
- 二叉搜索树平均插入和查找的时间为1.39logn
- 二叉搜索树平均情况运行时间依然是很快
6、参考
- 算法导论 二叉搜索树