二叉排序树
数据结构中，线性表分为无序线性表和有序线性表。
无序线性表的数据是杂乱无序的，所以在插入和删除时，没有什么必须遵守的规则，可以插入在数据尾部或者删除在数据尾部。但是在查找的时候，需要遍历整个数据表，导致无序线性表的查找效率低。
有序线性表的数据则相反，查找数据时的时候因为数据是有序的，可以用二分法、插值法、斐波那契查找法来实现。但是，当进行插入和删除操作时，需要维护表中数据的有序性，会耗费大量的时间。
那么，我们希望找到一种数据结构，既可以有较高的插入和删除效率，并且具备较高的查找效率，因此，二叉排序树应运而生。
二叉排序树定义
二叉排序树（Binary Sort Tree），又称二叉查找树（Binary Search Tree），也称二叉搜索树。二叉排序树或者是一棵空树，或者是具有下列性质的二叉树：
（1）若左子树不空，则左子树上所有结点的值均小于或等于它的根结点的值；
（2）若右子树不空，则右子树上所有结点的值均大于或等于它的根结点的值；
（3）左、右子树也分别为二叉排序树；
构造一棵二叉排序树
现有序列：61 87 59 47 35 73 51 98 37 93
构造过程如下：
1）索引 i = 0，A[i] = 61，结点61作为根结点，如图2.1：
2）索引 i = 1，A[1] = 87, 87 > 61，且结点61右孩子为空，故81为61结点的右孩子，如图2.2：
3）索引 i = 2，A[i] = 59，59 <
61，且结点61左孩子为空，故59为61结点的左孩子，如图2.3：
4）索引 i = 3，A[3] = 47，47 < 59，且结点59左孩子为空，故47为59结点的左孩子，如图2.4：
5）索引 i = 4，A[4] = 35，35 < 47，且结点47左孩子为空，故35为47结点的左孩子，如图2.5：
采用同样规则遍历整个数组得到如图2.6所示的一棵排序二叉树。
二叉排序树查找
由二叉树的递归定义性质，二叉排序树的查找同样可以使用如下递归算法查找。
如果树是空的，则查找结束，无匹配。
如果被查找的值和根结点的值相等，查找成功。否则就在子树中继续查找。如果被查找的值小于根结点的值就选择左子树，大于根结点的值就选择右子树。
在理想情况下，每次比较过后，树会被砍掉一半，近乎折半查找。
遍历打印可以使用中序遍历，打印出来的结果是从小到大的有序数组。
查找代码：
static class Node {
Object data;
Node parent;
Node left;
Node right;
public Node(Object data, Node parent, Node left, Node right) {
this.data = data;
this.parent = parent;
this.left = left;
this.right = right;
}
@Override
public String toString() {
return "[data=" + data + "]";
}
@Override
public boolean equals(Object obj) {
if (this == obj) {
return true;
}
if (obj.getClass() == Node.class) {
Node target = (Node) obj;
return data.equals(target.data) && left == target.left && right == target.right && parent == target.parent;
}
return false;
}
}
// 根据给定的值搜索节点
public Node getNode(T ele) {
// 从根节点开始搜索
Node p = root;
while (p != null) {
int cmp = ele.compareTo(p.data);
// 如果搜索的值小于当前p节点的值
if (cmp < 0) {
// 向左子树搜索
p = p.left;
} else if (cmp > 0) {
// 如果搜索的值大于当前p节点的值
// 向右子树搜索
p = p.right;
} else {
return p;
}
}
return null;
}
对于图2.6所示的二叉排序树，若查找结点key为47则可以查找成功，若查找结点key为75，树中不存在key为75的结点，故查找失败。
二叉排序树插入
二叉排序的插入是建立在二叉排序的查找之上的，插入一个结点，就是通过查找发现该结点合适插入位置，把结点直接放进去。
由此可以得出二叉排序树插入规则如下：
若查找的key已经有在树中，则parent指向该数据结点。
若查找的key没有在树中，则parent指向查找路径上最后一个结点。
例如：若在图2.6展示的二叉排序树中插入结点数据为60的结点。
首先查找结点数据为60的结点，二叉排序树中不存在结点为60的结点，因此查找失败。此时查找指针p指向查找路径最后一个结点即指向59结点。由于60>59且59结点右子树为空，故将60结点作为59结点的右孩子，插入完成。插入后的二叉排序树如图2.8所示。
插入代码：
// 添加节点
public void add(T ele) {
// 如果根节点为null
if (root == null) {
root = new Node(ele, null, null, null);
} else {
Node current = root;
Node parent = null;
int cmp = 0;
// 搜索合适的叶子节点，以该叶子节点为父节点添加新节点
do {
parent = current;
cmp = ele.compareTo(current.data);
// 如果新节点的值大于当前节点的值
if (cmp > 0) {
// 以右子节点作为当前节点
current = current.right;
} else {
// 如果新节点的值小于当前节点的值
// 以左节点作为当前节点
current = current.left;
}
}while (current != null);
// 创建新节点
Node newNode = new Node(ele, parent, null, null);
// 如果新节点的值大于父节点的值
if (cmp > 0) {
// 新节点作为父节点的右子节点
parent.right = newNode;
} else {
// 如果新节点的值小于父节点的值
// 新节点作为父节点的左子节点
parent.left = newNode;
}
}
}
二叉排序树删除
二叉树的删除可不再像二叉树的插入那么容易了，以为删除某个结点以后，会影响到树的其它部分的结构。
删除的时候需要考虑以下几种情况：
1）删除结点为叶子结点；
2）删除的结点只有左子树；
3）删除的结点只有右子树
4）删除的结点既有左子树又有右子树。
考虑前三种情况，处理方式比较简单。
例如：若要删除图2.8中的结点93，则直接删除该结点即可。删除后二叉排序树如图2.9所示：
若要删除的结点为结点35，结点35只有右子树，只需删除结点35，将右子树37结点替代结点35即可。删除后的二叉排序树如图2.10所示：
删除只有左子树的结点与此情况类似。
情况4相对比较复杂，对于待删除结点既有左子树又有右子树的情形，最佳办法是在剩余的序列中找到最为接近的结点来代替删除结点。这种代替并不会影响到树的整体结构。那么最为接近的结点如何获取呢？
可以采用中序遍历的方式来得到删除结点的前驱和后继结点。选取前驱结点或者后继结点代替删除结点即可。
例如：待删除的结点为47，图2.8中二叉排序树的中序遍历序列为35 37 47 51 59 60 61 73 87 93 98。则结点47的前驱结点为37，则直接将37结点替代47结点即可。替换后的二叉排序树如图2.11所示：
删除代码：
// 删除节点
public void remove(T ele) {
// 获取要删除的节点
Node target = getNode(ele);
if (target == null) {
return;
}
// 左、右子树为空
if (target.left == null && target.right == null) {
// 被删除节点是根节点
if (target == root) {
root = null;
} else {
// 被删除节点是父节点的左子节点
if (target == target.parent.left) {
// 将target的父节点的left设为null
target.parent.left = null;
} else {
// 将target的父节点的right设为null
target.parent.right = null;
}
target.parent = null;
}
} else if (target.left == null && target.right != null) {
// 左子树为空，右子树不为空
// 被删除节点是根节点
if (target == root) {
root = target.right;
} else {
// 被删除节点是父节点的左子节点
if (target == target.parent.left) {
// 让target的父节点的left指向target的右子树
target.parent.left = target.right;
} else {
// 让target的父节点的right指向target的右子树
target.parent.right = target.right;
}
// 让target的右子树的parent指向target的parent
target.right.parent = target.parent;
}
} else if (target.left != null && target.right == null) {
// 左子树不为空，右子树为空
// 被删除节点是根节点
if (target == root) {
root = target.left;
} else {
// 被删除节点是父节点的左子节点
if (target == target.parent.left) {
// 让target的父节点的left指向target的左子树
target.parent.left = target.left;
} else {
// 让target的父节点的right指向target的左子树
target.parent.right = target.left;
}
// 让target的左子树的parent指向target的parent
target.left.parent = target.parent;
}
} else {
// 左、右子树都不为空
// leftMaxNode用于保存target节点的左子树中值最大的节点
Node leftMaxNode = target.left;
// 搜索target节点的左子树中值最大的节点
while (leftMaxNode.right != null) {
leftMaxNode = leftMaxNode.right;
}
// 从原来的子树中删除leftMaxNode节点
leftMaxNode.parent.right = null;
// 让leftMaxNode的parent指向target的parent
leftMaxNode.parent = target.parent;
// 被删除节点是父节点的左子节点
if (target == target.parent.left) {
// 让target的父节点的left指向leftMaxNode
target.parent.left = leftMaxNode;
} else {
// 让target的父节点的right指向leftMaxNode
target.parent.right = leftMaxNode;
}
leftMaxNode.left = target.left;
leftMaxNode.right = target.right;
target.parent = target.left = target.right = null;
}
}
总结
二叉排序树是一种查找与插入效率均较为高效的数据结构，同时，二叉排序树也是二叉树学习中的重点与难点。希望通过本篇的学习能够掌握二叉排序树的查找、插入与删除等基本操作。
