Java 算法之二叉排序树
二叉排序树（BST）的定义
二叉排序树或者是空树，或者是满足以下性质的二叉树：
- 若它的左子树不空，则左子树上所有关键字的值均小于根关键字的值。
- 若它的右子树不空，则右子树上所有关键字的值均大于根关键字的值。
- 左右子树又各是一棵二叉排序树。
说明：由二叉排序树的定义可以知道，如果输出二叉排序树的中序遍历序列，则这个序列是递增有序的。
二叉排序树的存储结构
二叉排序树通常采用二叉链表进行存储，其结点类型定义与一般的二叉树类似。
二叉树结点的声明：
static final class Entry<T extends Comparable<T>>{
//保存的数据
private T item;
//左子树
private Entry<T> left;
//右子树
private Entry<T> right;
//父节点
private Entry<T> parent;
Entry(T item,Entry<T> parent){
this.item = item;
this.parent = parent;
}
}
类属性：
//根节点
private Entry<T> root;
//数据量
private int size = 0;
二叉排序树的基本算法
-
查找关键字的算法
显然，要找的关键字要么在左子树上，要么在右子树上，要么在根结点上。由二叉排序树的定义可以知道，根结点中的关键字将所有关键字分成了两部分，即大于根结点中关键字的部分和小于根结点中关键字的部分。可以将待查关键字先和根结点中的关键字比较，如果相等则查找成功；如果小于则到左子树中去查找，无须考虑右子树中的关键字；如果大于则到右子树中去查找，无须考虑左子树中的关键字。如果来到当前树的子树根，则重复上述过程；如果来到了结点的空指针域，则说明查找失败。可以看出这个过程和折半查找法十分相似，实际上折半查找法的判定树就是一棵二叉排序树。
/** * 判断是否存在该元素 * @param item 查找元素 * @return 结果 */ public boolean contains(T item){ return getEntry(item) != null; } /** * 获取节点节点 * @param item 获取节点 * @return 获取到的节点，可能为null */ private Entry<T> getEntry(T item){ Entry<T> t = root; int ret; //从根节点开始遍历 for (;t != null;){ ret = item.compareTo(t.item); if (ret < 0) t = t.left; else if (ret > 0) t = t.right; else return t; } return null; } -
插入关键字的算法
二叉排序树是一个查找表，插入一个关键字首先要找到插入位置。对于一个不存在于二叉排序树中的关键字，其查找不成功的位置即为该关键字的插入位置。
/** * 添加元素 * @param item 待添加元素 * @return 已添加元素 */ public T put(T item){ //每次添加数据的时候都是从根节点向下遍历 Entry<T> t = root; if (t == null){ //当前的叉树树的为空，将新节点设置为根节点，父节点为null root = new Entry<>(item,null); size++; return root.item; } //自然排序结果，如果传入的数据小于当前节点返回-1，大于当前节点返回1，否则返回0 int ret = 0; //记录父节点 Entry<T> p = t; while (t != null){ //与当前节点比较 ret = item.compareTo(t.item); p = t; //插入节点比当前节点小，把当前节点设置为左子节点，然后与左子比较，以此类推找到合适的位置 if (ret < 0) t = t.left; //大于当前节点 else if (ret > 0) t = t.right; else { //相等就把旧值覆盖掉 t.item = item; return t.item; } } //创建新节点 Entry<T> e = new Entry<>(item,p); //根据比较结果将新节点放入合适的位置 if (ret < 0) p.left = e; else p.right = e; size++; return e.item; } -
删除关键字的操作
挡在二叉排序树中删除一个关键字时，不能把以该关键字所在的结点为根的子树都删除，而是只删除这一个结点，并保持二叉排序树的特性。
假设在二叉排序树上被删除的结点为 p，f 为其双亲结点，则删除结点 p 的过程分为以下 3 种情况。
1) p 结点为叶子结点。由于删除叶子结点后不会破坏二叉排序树的特性，因此直接删除即可。
2) p 结点只有右子树而无左子树，或者只有左子树而无右子树。将删除结点的父结点的左结点（右结点）指向删除结点的子结点，将左结点（右结点）指向删除结点的父节点。
3) p 结点既有左子树又有右子树。找到删除节点的前驱节点或后继节点，然后将前驱或后继节点的值赋给删除节点，然后将前驱或后继节点删除。本质是删除前驱或后继节点。
前驱节点的特点：
1）删除的左子节点没有右子节点，那么左子节点即为前驱节点；
2）删除节点的左子节点有右子节点，那么最右边的最后一个节点即为前驱节点。
后继节点的特点：
与前驱节点刚好相反，总是右子节点，或则右子节点的最左子节点；例如：删除节点为 c ，那么前驱节点为 m，后继节点为 n。
/**
* 删除元素
* @param item 删除元素
* @return 删除结果
*/
public boolean remove(T item){
//获取删除节点
Entry<T> delEntry = getEntry(item);
if (delEntry == null) return false;
//删除节点的父节点
Entry<T> p = delEntry.parent;
size--;
//情况1：没有子节点
if (delEntry.left == null && delEntry.right == null){
//删除节点为根节点
if (delEntry == root){
root = null;
}else {//非根节点
//删除的是父节点的左节点
if (delEntry == p.left){
p.left = null;
}else {//删除右节点
p.right = null;
}
}
//情况2：删除的节点只有左节点
}else if (delEntry.right == null){
Entry<T> lc = delEntry.left;
//删除的节点为根节点，将删除节点的左节点设置成根节点
if (p == null) {
lc.parent = null;
root = lc;
} else {//非根节点
if (delEntry == p.left){//删除左节点
p.left = lc;
}else {//删除右节点
p.right = lc;
}
lc.parent = p;
}
//情况3：删除节点只有右节点
}else if (delEntry.left == null){
Entry<T> rc = delEntry.right;
//删除根节点
if (p == null) {
rc.parent = null;
root = rc;
}else {//删除非根节点
if (delEntry == p.left)
p.left = rc;
else
p.right = rc;
rc.parent = p;
}
//情况4：删除节点有两个子节点
}else {//有两个节点,找到后继节点，将值赋给删除节点，然后将后继节点删除掉即可
Entry<T> successor = successor(delEntry);//获取到后继节点
delEntry.item = successor.item;
//后继节点为右子节点
if (delEntry.right == successor){
//右子节点有右子节点
if (successor.right != null) {
delEntry.right = successor.right;
successor.right.parent = delEntry;
}else {//右子节点没有子节点
delEntry.right = null;
}
}else {//后继节点必定是左节点
successor.parent.left = null;
}
return true;
}
//让gc回收
delEntry.parent = null;
delEntry.left = null;
delEntry.right = null;
return true;
}
/**
* 获取节点节点
* @param item 获取节点
* @return 获取到的节点，可能为null
*/
private Entry<T> getEntry(T item){
Entry<T> t = root;
int ret;
//从根节点开始遍历
for (;t != null;){
ret = item.compareTo(t.item);
if (ret < 0)
t = t.left;
else if (ret > 0)
t = t.right;
else
return t;
}
return null;
}
/**
* 查找后继节点
* @param delEntry 删除节点
* @return 后继节点
*/
private Entry<T> successor(Entry<T> delEntry) {
Entry<T> r = delEntry.right;//r节点必定不为空
while (r.left != null){
r = r.left;
}
return r;
}
