二叉排序树(BST)
首先二叉排序树可以认为是Biary Sort Tree或者Biary Search Tree的缩写,也可以解释为二叉查找树,还可以称之为二叉搜索树。
引出
对于之前的线性存储结构比如数组、链表,他们有一个通病就是查找效率低下,就算使用二分查找或者插值查找亦或者斐波那契查找,也不能提升太多在海量数据下的查找效率。
而树结构查找天然就有很大的优势,所以自然就引出了二叉排序树这个概念,来解决传统线性结构的查找效率低下的问题。
定义
一棵空树,或者是具有下列性质的二叉树:
- 若左子树不空,则左子树上所有结点的值均小于它的根结点的值;
- 若右子树不空,则右子树上所有结点的值均大于它的根结点的值;
- 左、右子树也分别为二叉排序树;
以上是百度百科粘贴的比较正式化的定义,这里我来翻译一下。
二叉排序树:一棵空二叉树或者这棵非空二叉树中的所有非叶子节点,它的左子节点要比当前节点小,它的右子节点要比当前节点大。
其实我看我翻译的这个定义,像极了之前堆排序中的大顶堆和小顶堆的折中。
在百度上的定义上是要求不可以有相同的值的,这里我们就按照教程中的规定,如果有相同的值可以放在其左子节点或者右子节点。
代码实现-基本结构搭建
节点类编写
还是老一套的三板斧:构造方法、遍历方法、toString方法
但是要注意的是遍历的方法需要时中序遍历,因为二叉排序树只有中序遍历的时候遍历出来时有序的。
class Node {
int value;
Node left;
Node right;
public Node(int value) {
this.value = value;
}
// 中序遍历
public void infixOrder() {
if (this.left != null) {
this.left.infixOrder();
}
System.out.println(this);
if (this.right != null) {
this.right.infixOrder();
}
}
@Override
public String toString() {
return "Node{" +
"value=" + value +
'}';
}
}
二叉排序树类编写
这里只需要写入root节点和封装中序遍历的方法就可以了
class BinarySortTree {
private Node root;
// 中序遍历
public void infixOrder() {
if (root != null) {
root.infixOrder();
} else {
System.out.println("树为空!");
}
}
}
代码实现-添加方法
添加的代码还是非常简单的,因为和删除节点比起来添加就是个弟弟。
思想
- 如果待添加节点比当前节点小
- 判断当前节点是否为空,为空直接将待添加节点添加到当前节点左边
- 如果不为空则将左子节点当作当前节点继续进行第一步
- 如果待添加节点比当前节点大
- 判断当前节点是否为空,为空直接将待添加节点添加到当前节点右
- 如果不为空则将右子节点当作当前节点继续进行第一步
图示
节点类代码
使用的递归来进行添加代码编写会比较简单
public void add(Node node) {
if (node == null) {
return;
}
// 传入节点的值,和当前子树的根节点的关系
if (node.value < this.value) {
if (this.left == null) {
this.left = node;
} else {
this.left.add(node);
}
} else {
if (this.right == null) {
this.right = node;
} else {
this.right.add(node);
}
}
}
二叉排序树类代码
public void add(Node node) {
if (root == null) {
root = node;
} else {
root.add(node);
}
}
代码实现-删除代码
之所以删除会比较复杂,是因为需要考虑的情况很多比如:删除叶子节点、删除只有一个子树的节点、删除有两个子树的节点
思想
这里接下来的分析设待删除节点为:target,待删除节点的父节点为parent
删除叶子节点
这个还是算比较简单的:
- 查找到target和parent
- 判断target是parent的左子树还是右子树
- 若为左子树则:
parent.left=null
- 若为右子树则:```parent.right=null``
删除有一个子树的非叶子节点
- 查找到target和parent
- 若target有左子树target.left
- 如果target是parent的左子树则:
parent.left = target.left
- 如果target是parent的右子树则:
parent.right = target.left
- 如果target是parent的左子树则:
- 若target有右子树target.right
- 如果target是parent的左子树则:
parent.left = target.rigth
- 如果target是parent的右子树则:
parent.right = target.right
- 如果target是parent的左子树则:
删除有两个子树的非叶子节点
- 查找到target
- 存储target的左子树的最大节点,或者存储target的右子树的最小(下面的代码中先会以右子树的最小节点为例,但是后面的课后练习中会再补上左子树最大的代码)
- 删除掉存储的节点
- 将target替换为存储的节点
target.value = temp
辅助方法编写
1. 查找target节点
节点类中的代码
public Node search(int value) {
if (value == this.value) {
return this;
} else if(value < this.value) {
// 查找的值小于当前节点,向左子树递归查找
// 如果左子节点为空,就代表找不到了
if (this.left == null) {
return null;
}
return this.left.search(value);
} else {
// 查找的值不小于
if (this.right == null) {
return null;
}
return this.right.search(value);
}
}
排序树类中的代码
// 查找要删除的节点
public Node search(int value) {
if (root == null) {
return null;
} else {
return root.search(value);
}
}
2. 查找parent节点
节点类代码
/**
* 查找要删除节点的父节点
* @param value 要查找的值
* @return 返回是查找的值的父节点
*/
public Node searchParent(int value) {
if ((this.left != null && this.left.value == value) ||
(this.right != null && this.right.value == value)) {
return this;
} else {
// 如果查找的值小于当前节点的值,且当前节点的左子节点不为空
if (value < this.value && this.left!= null) {
return this.left.searchParent(value);
} else if (value >= this.value && this.right != null) {
return this.right.searchParent(value);
} else {
return null;
}
}
}
排序树类代码
// 查找要删除的节点的父节点
public Node searchParent(int value) {
if (root == null) {
return null;
} else {
return root.searchParent(value);
}
}
3. 查找传入节点的最小节点返回并删除
这个方法是直接写在排序树类中的
/**
* 删除并返回传入节点的最子小节点的值
* @param node 传入的节点
* @return 传入节点最小子节点值
*/
public int delRightTreeMin(Node node) {
Node target = node;
// 循环的查找左节点就会找到最小值
while (target.left != null) {
target = target.left;
}
// 这时候target就指向了最小的节点
// 删除最小节点
delNode(target.value);
return target.value;
}
删除方法代码
这个代码的分析实在是写不动,难度倒是不高就是逻辑太复杂了,是完全按照上面的思想写的,但愿以后复习的我可以看懂。
public void delNode(int value) {
if (root == null) {
return;
}
// 找到要删除的节点
Node targetNode = search(value);
// 如果没有找到
if (targetNode == null) {
return;
}
// 树中只有一个节点
if (root.left == null && root.right == null) {
root = null;
return;
}
Node parent = searchParent(value);
// 如果要删除的节点是叶子节点
if (targetNode.left == null && targetNode.right == null) {
if (parent.left != null && targetNode == parent.left) {
parent.left = null;
}
if (parent.right != null && targetNode == parent.right) {
parent.right = null;
}
} else if (targetNode.left != null && targetNode.right != null) {
// 有两颗子树
targetNode.value = delRightTreeMin(targetNode.right);
} else {
// 只有一个子树
// 如果要删除的节点有左子节点
if (targetNode.left != null) {
if (parent == null) {
root = targetNode.left;
return;
}
if (parent.left != null && targetNode == parent.left) {
parent.left = targetNode.left;
}
if (parent.right != null && targetNode == parent.right) {
parent.right = targetNode.left;
}
} else {
if (parent == null) {
root = targetNode.right;
return;
}
if (parent.left != null && targetNode == parent.left) {
parent.left = targetNode.right;
}
if (parent.right != null && targetNode == parent.right) {
parent.right = targetNode.right;
}
}
}
}
课后作业-实现删除两个子树的节点的第二种方案
上面代码是用的将右子树中的最小的来替换target,这里就是要求使用左子树中最大的来替换target
先重新写一下寻早最小值的方法改造成找最大值删除,其实也很简单
/**
* 删除并返回传入节点的最大子节点的值
* @param node 传入的节点
* @return 传入节点最大子节点值
*/
public int delLeftTreeMax(Node node) {
Node target = node;
// 循环的查找左节点就会找到最小值
while (target.right != null) {
target = target.right;
}
// 这时候target就指向了最小的节点
// 删除最小节点
delNode(target.value);
return target.value;
}
再改变一下delNode中的调用的代码就好了
将之前的targetNode.value = delRightTreeMin(targetNode.right);
改为下述代码就完成了!
targetNode.value = delLeftTreeMax(targetNode.left);
二叉平衡排序树(AVL)
引出
比二叉排序树多了个平衡,那为什么二叉排序树做不到平衡呢?
先看一组例子:将int arr[] = {1,2,3,4,5,6,7}
依次添加到一颗二叉排序树中
结果会是
虽然再名义上还是一棵二叉树但是它的内心早就变成一个单链表了。
这就引出了平衡这一概念,因为树高度越低查找效率越高,这种一条龙形态的二叉排序树是最不想看到的。
可以将二叉排序树做到平衡的算法有很多比如:AVL算法、红黑树、替罪羊树等等。
这里教程中的介绍的是AVL算法,我感觉介绍的比较浅,虽然我十分喜欢红黑树,但是这里还是根据教程只写AVL的算法。才不是我太菜看不懂红黑树呢?
定义
二叉平衡排序树首先是一棵二叉排序树,且它的所有节点具有一个属性为平衡因子,当所有的节点的平衡因子仅为0,1,-1时称这个二叉排序树为二叉平衡排序树。
平衡因子 = 右子树的高度 - 左子树的高度
思路
一棵二叉平衡排序树必须的先是一棵二叉排序树,前者对于后者也仅仅是多了平衡的处理。其实难点也在这个平衡上。
实现调整平衡而又不破坏二叉排序树的结构的方法是旋转,旋转分为左旋,右旋和双旋。
左旋
左旋转用于处理右子树比左子树高的情况,也就是根节点的平衡因子大于1的情况
操作步骤:
- 新建一个节点为newNode,存储当前节点
- 将newNode的左子树设为当前节点的左子树
- 将newNode的右子树设为当前节点的右子树的左子树
- 将当前节点的值替换为当前节点的右子树的值
- 将当前节点的左子树设置为newNode
- 将当前节点的右子树设置为当前节点的右子树的右子树
图中右树的绿色框内是新建的节点,橘色框中是当前节点的右子节点。
右旋
左旋转用于处理左子树比右子树高的情况,也就是根节点的平衡因子小于-1的情况
操作步骤和左旋大同小异,这里就不再啰嗦一遍了只展示图例。
双旋
双旋转故名思意就是左旋和右旋结合,没有新的知识。
这里只介绍一下什么时候用双旋,和为什么会需要使用双旋。
先看一个例子:arr[] = {10, 11, 7, 6, 8, 9}
使用这个数组构建的二叉排序树,是需要使用右旋来进行平衡调整的,但是单独的右旋是不能将其调整平衡的,具体请情况看图示。
可以看到进行右旋之后二叉树并没有平衡它的根节点平衡因子由-2变为了2还是不平衡
这时候就要进行双旋的处理了。
也就是如果需要进行右旋的时候左子树的平衡因子>0,则要先对左子树进行左旋然后再对根节点进行右旋,这个过程就成为双旋。
代码实现
求树的高度
这里的height很巧妙的用了递归
// 返回当前节点的高度,该节点为根节点的高度
public int height() {
return Math.max(left == null ? 0 : left.height(), right == null ? 0 : right.height()) + 1;
}
// 返回左子树的高度
public int leftHeight() {
if (left == null) {
return 0;
}
return left.height();
}
// 返回右子树的高度
public int rightHeight() {
if (right == null) {
return 0;
}
return right.height();
}
左旋右旋实现
// 左旋
private void leftRotate() {
// 创建新的节点,以当前根节点的值
Node newNode = new Node(value);
// 把新的节点的左子树,设置成当前节点的左子树
newNode.left = left;
// 把新的节点的右子树设置成当前节点的右子树的左子树
newNode.right = right.left;
// 把当前节点的值替换成右子节点的值
value = right.value;
// 把当前节点的右子树设置成右子树的右子树
right = right.right;
// 把当前节点的左子节点设置为新的节点
left = newNode;
}
public void rightRotate() {
Node newNode = new Node(value);
newNode.right = right;
newNode.left = left.right;
value = left.value;
left = left.left;
right = newNode;
}
add方法的升级
在添加元素时判断平衡因子是如何旋转来保持平衡,注意旋转的时候要判断双旋转的情况
public void add(Node node) {
if (node == null) {
return;
}
// 传入节点的值,和当前子树的根节点的关系
if (node.value < this.value) {
if (this.left == null) {
this.left = node;
} else {
this.left.add(node);
}
} else {
if (this.right == null) {
this.right = node;
} else {
this.right.add(node);
}
}
// 这之后的代码时保持平衡的代码
// 当添加完一个节点后,如果右子树的高度-左子树的高度>1 左旋转
if (rightHeight() - leftHeight() > 1) {
if (right != null && right.leftHeight() > right.rightHeight()) {
right.rightRotate(); // 右旋转
}
leftRotate(); // 左旋转
return;
}
if (leftHeight() - rightHeight() > 1) {
if (left != null && left.rightHeight() > left.leftHeight()) {
left.leftRotate(); // 左旋转
}
rightRotate(); // 右旋转
}
}
Q.E.D.