二叉排序树
2019-01-27 本文已影响107人
柯基去哪了
一 序
学习完二叉树的遍历方法、运用递归与迭代的手段完成树的深度、叶子节点数与节点总数目相关方法后。在此基础上我们进一步学习一个结构--二叉排序树(Binary Search Tree or Binary Sort Tree)简称 BST。这一数据结构在用于查找的时候能够体现出优越性，理想状态下的查找效率能达到 O(logn)。可作为符号表实现的可选方案。
二叉排序树有几个很明显的特征：
- 根节点的左子树中的所有节点值均小于根节点本身的值。
- 根节点的右子树中的所有节点值均大于根节点本身的值。
- 根节点的左右子树也均是二叉排序树。
- 没有键值相等的节点。
二 相关方法
2.1 插入
在生成一个二叉排序树的时候，可以使用迭代或者递归的方式，任意选取一个节点值作为跟节点进行插入操作。如果前面已经能够理解二叉树的一系列遍历算法，那么在这里编写对应的插入方法会比较容易理解
当我们给出一个数组的时候，可以先自己画出对应生成的二叉排序树的结构，比如出这样的一个数组：
Integer[] array = new Integer[]{6, 5, 1, 9, 3, 4, 10};
insertBST.png
梳理一下其元素插入的逻辑：
- insert操作得到的第一个节点是 6，将 6 直接作为二叉树的根节点。
- 得到第二个节点 5，5 小于 6，安插到 6 的左子树。
- 第三个节点 1，与根节点相比小于，进而被安插到左子树，左子树第一层级存在了节点 5。1 仍然小于 5，所以被安插作为 5 的左子节点。单独看节点 1 和 5 之间的关系，它们也满足 二叉排序树的规则。
- 第四个元素 9，大于根节点 6，此时 6 的右子树为空，直接安插作为根节点 6 的右子节点。
- 第五个元素 10，大于根节点 6 且大于 6 的当前第一个右子节点 9，所以会被安插到 9 的右子节点的位置。
insertProcess.png
在完成手动的作图后，可以开始编写代码了。目测了一下应该是有迭代和递归两种写法的。这里贴出来迭代法的实现。
/**
* 二叉查找树 Binary Search Tree--基于二叉树的一种数据结构，以每个节点为根，其左子树的 data 域均小于根节点值；而其右子树的 data 域均大于根节点值。
* @author carpeng.gao@qunar.com
* @date 2019/1/21 14:32
**/
public class BST {
private BNode<Integer> root = null;
public void insert(Integer[] params) {
for (Integer param : params) {
this.insert(new BNode<>(param));
}
}
/**
* 二叉查找树的插入算法--迭代法
* @param bNode 待插入节点
*/
public void insert(BNode<Integer> bNode) {
if (null == bNode)
return;
if (root == null) {
root = bNode;
return;
}
BNode<Integer> temp = root;
while (true) {
if (bNode.getData() > temp.getData()) { // 插入节点的值大于根节点值
if (temp.getRchild() == null) { // 右子树为空
temp.setRchild(bNode);
break;
} else {
temp = temp.getRchild();
}
} else if (bNode.getData() < temp.getData()) {// 插入节点值小于根节点值
if (temp.getLchild() == null) { // 左子树为空
temp.setLchild(bNode);
break;
} else {
temp = temp.getLchild();
}
}
}
}
}
2.2 查找
在生成二叉树的方法了解清楚之后，我们也可以很快理解二叉排序树的查找方法。理想的二叉排序树的查找时间效率能达到O(logn)级别。
得到一个入参 N，要求检索二叉排序树X中是否包含这个元素 N。思路整理如下：
- 检查二叉树 X 的根节点 a 与入参节点 N 的大小关系，如果二者值相等，那么找到了目标值。
- 如果 N 大于 a 的值，那么进入根节点 a 的右子树继续查找；如果 N 小于 a 的值，那么进入根节点 a 的左子树继续查找。进入子树后检索操作同步骤1。直到找到这个节点值或者对应子节点为空(如果到了子节点为空的时候，即说明二叉排序树中不存在这个节点)。
search.png
如下为由迭代方法实现的二叉排序树搜索方法：
/**
* 二叉查找树的查找方法
* @param param 目标值
* @return
*/
public Integer get(Integer param) {
if (null == param)
return null;
BNode<Integer> temp = root;
while (true) {
if (temp.getData() > param) {
if (temp.getLchild() != null)
temp = temp.getLchild();
else
return null;
} else if (temp.getData() < param) {
if (temp.getRchild() != null)
temp = temp.getRchild();
else
return null;
} else {
return temp.getData();
}
}
}
2.3 删除
删除指定节点的方法，这里比较复杂的是需要删除的指定节点存在左右子节点的时候。
总的来说存在如下四种情况
- 要删除的目标节点没有左右子节点，这个时候直接把目标节点的父节点对应的的左(右)子树置空即可。
- 要删除的目标节点有左子节点而没有右子节点，这个时候把目标节点的左子节点置为目标节点的左(右)子树。
- 要删除的目标节点有右子节点而没有左子节点，这个时候把目标节点的右子节点置为目标节点的左(右)子树。
- 要删除的目标节点同时存在左右两个子树，是二叉排序树中最麻烦的一个节点处理--即当前找到的待删除节点，既有右子树Pr，又有左子树Pl：有两种处理方案
- 直接令待删除节点的左子树Pl替代到当前待删除节点的位置，然后将右子树Pr放到Pl子树中序遍历的最后一个节点的右子树上。
- 第二种办法依赖于线索二叉树的前驱/后继节点的定位。暂时不表
BSTRmove.png
这个迭代版本的删除方法没有经过充分的测试，仅供参考：
/**
* 二叉查找树的删除方法
* @param param 待删除数值
* @return 删除成功返回 true，否则返回 false
*/
public boolean remove(Integer param) {
if (null == param)
return true;
BNode<Integer> pre = null;
int rl = 0;
BNode<Integer> temp = root;
while (true) {
if (temp.getData() > param) {
pre = temp;//保存前一个节点--即保存一个父节点
temp = temp.getLchild();
rl = 1;//表示走到了左子树
} else if (temp.getData() < param) {
pre = temp;
temp = temp.getRchild();
rl = 2;//表示走到了右子树
} else {
//找到了要删除的节点
if (temp.getRchild() == null && temp.getLchild() == null) {
// 目标节点没有任何子节点
if (rl == 1)
pre.setLchild(null);
else if (rl == 2)
pre.setRchild(null);
return true;
}
if (temp.getRchild() != null && temp.getLchild() == null) {
//目标节点有右子节点而没有左子节点
if (rl == 1)
pre.setLchild(temp.getRchild());
else if (rl == 2)
pre.setRchild(temp.getRchild());
return true;
} else if (temp.getRchild() == null && temp.getLchild() != null) {
//目标节点有左子节点而没有右子节点
if (rl == 1)
pre.setLchild(temp.getLchild());
else if (rl == 2)
pre.setRchild(temp.getLchild());
return true;
} else {
//目标节点的左右子节点均存在
/**
* 这里是二叉排序树中最麻烦的一个节点处理--即当前找到的待删除节点，既有右子树Pr，又有左子树Pl：有两种处理方案
* 1. 直接令待删除节点的左子树Pl替代到当前待删除节点的位置，然后将右子树Pr放到Pl子树中序遍历的最后一个节点的右子树上。
* 2. 第二种办法依赖于线索二叉树的前驱/后继节点的定位。暂时不表
*/
if (rl == 1) {
pre.setLchild(temp.getLchild());
} else if (rl == 2) {
pre.setRchild(temp.getLchild());
}
BNode<Integer> inOrderLastNode = getInOrderLastNode(temp.getLchild());
inOrderLastNode.setRchild(temp.getRchild());
return true;
}
}
}
}
三 总结
二叉排序树是在二叉树的基础上衍生出来的一种数据结构，具有二叉树的基本特性。其元素的编排安放位置，决定了它是一种适合存储和查找无序列表。其查找方法的理想的时间复杂度是O(logn)。
search2.png
请注意这个 理想的查找时间复杂度，这个要取决于当前二叉排序树的左右子树深度(实际上受限于元素的插入和删除影响)。因此在实际的程序编写中，一般不会直接使用二叉排序树来保存元素，而是使用其进一步的变体：平衡二叉树，这种思想的实现结构有 AVL、红黑树等等，这一系列的变体结构，主要的修正是在二叉排序树执行了插入和删除操作之后会使用旋转等一系列操作修改当前树结构，以保证二叉排序树的平衡性，平衡性 是指二叉排序树的左右子树的深度查的绝对值小于等于1。
