文章目录
-
- 1 引言
-
- 1.1 为什么要有树结构？
- 2 二叉搜索树
-
- 2.1 定义
- 2.2 性质
- 2.3 节点结构
-
- 代码定义：
- 2.4 创建二叉搜索树
- 2.5 查找
-
- 查找流程：
- 查找代码：
- 2.6 插入
-
- 插入流程：
- 图解过程：
- 代码实现：
- 2.7 删除
-
- （1）删除节点为叶子节点
- （2） 删除的节点只有左子树
- （3）删除的节点只有右子树
- （4） 删除的节点既有左子树又有右子树。
- 删除代码：
- 3 平衡二叉树
-
- 3.1 定义
-
- 3.1.1 AVL
- 3.2 平衡因子
- 3.3 节点结构
- 3.4 左旋与右旋
-
- （1） 左旋
- 图解过程：
- （2）右旋
- 图解过程：
- 3.5 插入
-
- （1） A的左孩子的左子树插入节点(LL)
- 图解过程：
- 代码实现：
- （2） A的右孩子的右子树插入节点(RR)
- 图解过程：
- 代码实现：
- （3） A的左孩子的右子树插入节点(LR)
- 图解过程：
- 代码实现：
- （4） A的右孩子的左子树插入节点(RL)
- 图解过程：
- 代码实现：
- 3.6 删除
- 代码实现：
- 4 结语
- 推荐阅读
1 引言 二叉树是数据结构中的重点与难点，也是应用较为广泛的一类数据结构。二叉树的基础知识在之前的数据结构——二叉树基础中已经详细介绍。本篇文章将着重介绍两类
二叉树，二叉搜索树和平衡二叉树。1.1 为什么要有树结构？
文章图片
文章图片
文章图片
2 二叉搜索树 2.1 定义
二叉搜索树又称二叉查找树，亦称为二叉排序树。设x为二叉查找树中的一个节点，x节点包含关键字key，节点x的key值记为key[x]。如果y是x的左子树中的一个节点，则key[y] <= key[x]；如果y是x的右子树的一个节点，则key[y] >= key[x]。2.2 性质
（1）若
左子树不空，则左子树上所有节点的值均小于它的根节点的值；（2）若
右子树不空，则右子树上所有节点的值均大于它的根节点的值；（3）
左、右子树也分别为二叉搜索树；例如：下图所示的
二叉树为一棵二叉搜索树。
文章图片
??例如：下图所示
不是一棵二叉搜索树，因为节点40的左孩子节点值为44，不满足二叉搜索树的定义。
文章图片
2.3 节点结构
二叉树的节点结构通常包含三部分，其中有：左孩子的指针，右孩子指针以及节点元素。节点的图示如下：
文章图片
文章图片
代码定义：
private class Node{public E e;
public Node left ,right;
public Node(E e){
this.e = e;
//元素
left = null;
//左孩子
right = null;
//右孩子
}
}
2.4 创建二叉搜索树
现有序列：
A = {61, 87, 59, 47, 35, 73, 51, 98, 37, 93}。根据此序列构造二叉搜索树过程如下：（1）i = 0，A[0] = 61，节点61作为根节点；
??（2）i = 1，A[1] = 87，87 > 61，且节点61
右孩子为空，故81为61节点的右孩子；??（3）i = 2，A[2] = 59，59 < 61，且节点61
左孩子为空，故59为61节点的左孩子；??（4）i = 3，A[3] = 47，47 < 59，且节点59
左孩子为空，故47为59节点的左孩子；??（5）i = 4，A[4] = 35，35 < 47，且节点47
左孩子为空，故35为47节点的左孩子；??（6）i = 5，A[5] = 73，73 < 87，且节点87
左孩子为空，故73为87节点的左孩子；??（7）i = 6，A[6] = 51，47 < 51，且节点47
右孩子为空，故51为47节点的右孩子；??（8）i = 7，A[7] = 98，98 < 87，且节点87
右孩子为空，故98为87节点的右孩子；??（9）i = 8，A[8] = 93，93 < 98，且节点98
左孩子为空，故93为98节点的左孩子；创建完毕后如下图中的二叉搜索树：
文章图片
2.5 查找
查找流程： （1）如果树是
空的，则查找结束，无匹配，返回false。（2）如果被查找的值和
节点的值相等，查找成功，返回true。（3）如果被查找的值
小于节点的值，递归查找左子树。（4）如果被查找的值
大于节点的值，递归查找右子树。查找代码：
//看二分搜索树中是否包含元素e
public boolean contains(E e){
return contains(root,e);
}//看以node为根的二分搜索树中是否包含元素e , 递归算法
private boolean contains(Node node , E e){
if(node == null){
return false;
}
if(e.compareTo(node.e) == 0){
return true;
}else if(e.compareTo(node.e) < 0){
return contains(node.left,e);
}else{//e.compareTo(node.e) > 0
return contains(node.right , e);
}
}
使用
二叉搜索树可以提高查找效率，其平均时间复杂度为O(log2n)。2.6 插入
插入流程： （1）先
检测该元素是否在树中已经存在。如果已经存在，则不进行插入；（2）
若元素不存在，则进行查找过程，并将元素插入在查找结束的位置。图解过程：
文章图片
文章图片
文章图片
代码实现：
//向node为根的二分搜索树中插入元素E，递归算法
//返回插入新节点后二分搜索树的根
//如果node为null，则新建一个节点，然后把传入的值赋值上
//如果compareTo > 0则向它右子树插入元素，反之向左子树
//左子树和右子树重新赋值后，返回的node还是以node为根的二分搜索树
private Node add(Node node , E e){
if(node == null){
size ++;
return new Node(e);
}if(e.compareTo(node.e) < 0){
node.left = add(node.left,e);
}else if(e.compareTo(node.e) > 0){
node.right = add(node.right,e);
}
return node;
}
2.7 删除
（1）删除节点为叶子节点 删除
叶子节点的方式最为简单，只需查找到该节点，直接删除即可。例如删除图2.4中的叶子节点37、节点51、节点60、节点73和节点93的方式是相同的。
文章图片
（2） 删除的节点只有左子树 删除的
节点若只有左子树，将节点的左子树替代该节点位置。例如：删除图2.4中的98节点：
文章图片
（3）删除的节点只有右子树 删除的节点若
只有右子树，将节点的右子树替代该节点位置。这种情况与删除左子树处理方式类似，不再赘述。（4） 删除的节点既有左子树又有右子树。
文章图片
??若删除的节点
既有左子树又有右子树，这种节点删除过程相对复杂。其流程如下：??（1）
遍历待删除节点的左子树，找到其左子树中的最大节点，即删除节点的前驱节点；??（2）将
最大节点代替被删除节点；??（3）
删除左子树中的最大节点；??（4）
左子树中待删除最大节点一定为叶子节点或者仅有左子树。按照之前情形删除即可。注：同样可以使用删除节点的
右子树中最小节点，即后继节点代替删除节点，此流程与使用前驱节点类似。删除代码：
//返回以node为根的二分搜索树的最小值所在的节点
private Node minimum(Node node){
if(node.left == null){
return node;
}
return minimum(node.left);
}//从二分搜索树中删除元素为e的节点
public void remove(E e){
root = remove(root, e);
}//删除以node为根的二分搜索树中值为e的节点，递归算法
//返回删除节点后新的二分搜索树的根
private Node remove(Node node , E e){
if(node == null){
return null;
}
if(e.compareTo(node.e) < 0){
node.left = remove(node.left ,e);
return node;
}else if(e.compareTo(node.e) > 0){
node.right = remove(node.right , e);
return node;
}else{// e == node.e//待删除节点左子树为空的情况
if(node.left == null){
Node rightNode = node.right;
node.right = null;
size --;
return rightNode;
}//待删除节点右子树为空的情况
if(node.right == null){
Node leftNode = node.left;
node.left = null;
size --;
return leftNode;
}//待删除节点左右子树均不为空的情况
//找到比待删除节点大的最小节点，即待删除节点右子树的最小节点
//用这个节点顶替待删除节点的位置
Node successor = minimum(node.right);
//因为要替换删除节点的位置，所以删除节点右子树的最小节点
successor.right = removeMin(node.right);
successor.left = node.left;
size++;
//将要删除节点的左右子树从二叉树中断开
node.left = node.right = null;
//维护二叉树长度
size--;
//返回新节点successor，让根节点指向新节点successor
return successor;
}
}//删除掉以node为根的二分搜索树中的最小节点
//返回删除节点后新的二分搜索树的根
//把左孩子删除后，返回右孩子
private Node removeMin(Node node){
if(node.left == null){
Node rightNode = node.right;
node.right = null;
size --;
return rightNode;
}
node.left = removeMin(node.left);
return node;
}3 平衡二叉树 3.1 定义
二叉搜索树一定程度上可以提高搜索效率，但是当原序列有序，例如序列A = {1，2，3，4，5，6}，构造二叉搜索树如下图所示。依据此序列构造的二叉搜索树为右斜树，同时二叉树退化成单链表，搜索效率降低为O(n)。
文章图片
??在此二叉搜索树中
查找元素6需要查找6次。二叉搜索树的查找效率取决于树的高度，因此保持树的高度最小，即可保证树的查找效率。同样的序列A，改为下图所示方式存储，查找元素6时只需比较3次，查找效率提升一倍。
文章图片
??可以看出当节点数目一定，保持树的
左右两端保持平衡，树的查找效率最高。这种左右子树的高度相差不超过1的树为平衡二叉树。
文章图片
文章图片
3.1.1 AVL
二分搜索树可能退化成链表，所以引入AVL平衡二叉树的概念，AVL树也是二分搜索树3.2 平衡因子
定义：某节点的
左子树与右子树的高度(深度)差即为该节点的平衡因子（BF,Balance Factor），平衡二叉树中不存在平衡因子大于1的节点。在一棵平衡二叉树中，节点的平衡因子只能取-1、1或者0。?
文章图片
下图
蓝色部分为平衡因子，黑色部分为层数
文章图片
3.3 节点结构
定义
平衡二叉树的节点结构：private class Node{
public K key;
public V value;
public Node left,right;
public int height;
//深度，这里计算每个结点的深度，通过深度的比较可得出是否平衡public Node(K key,V value){//默认构造函数
this.key = key;
this.value = https://www.it610.com/article/value;
left = null;
right = null;
height = 1;
}
}
对于给定
结点数为n的AVL树，最大高度为O(log2n).3.4 左旋与右旋
（1） 左旋 如下图所示的
平衡二叉树
文章图片
如在此平衡二叉树
插入节点62，树结构变为：
文章图片
??可以得出
40节点的左子树高度为1，右子树高度为3，此时平衡因子为-2，树失去平衡。为保证树的平衡，此时需要对节点40做出旋转，因为右子树高度高于左子树，对节点进行左旋操作，流程如下：??（1）
节点的右孩子替代此节点位置??（2）
右孩子的左子树变为该节点的右子树??（3）
节点本身变为右孩子的左子树图解过程：
文章图片
文章图片
（2）右旋
右旋操作与左旋类似，操作流程为：??（1）
节点的左孩子代表此节点??（2）
节点的左孩子的右子树变为节点的左子树??（3）将此
节点作为左孩子节点的右子树。图解过程：
文章图片
文章图片
3.5 插入
假设一颗
AVL 树的某个节点为A，有四种操作会使 A 的左右子树高度差大于 1，从而破坏了原有AVL 树的平衡性 。平衡二叉树插入节点的情况分为以下四种：（1） A的左孩子的左子树插入节点(LL) 例如：下图所示的
平衡二叉树：
文章图片
节点A的左孩子为B，B的左子树为D，无论在节点D的左子树或者右子树中插入F均会导致节点A失衡。因此需要对节点A进行旋转操作。A的平衡因子为2，值为正，因此对A进行右旋操作。图解过程：
文章图片
文章图片
代码实现：
//LL
//不平衡的原因是左侧的左侧多添加了一个节点
if(balanceFactor > 1 && getBalanceFactor(node.left) >=0){
//返回递归的上一层，继续处理上一层的节点
//至此，新的根节点，就已经保证了，以这个根节点为根的，
//整棵二叉树即是一个二分搜索树，又是一棵平衡二叉树
return rightRotate(node);
}//获得节点node的平衡因子
private int getBalanceFactor(Node node){
if(node == null){
return 0;
}
return getHeight(node.left) - getHeight(node.right);
}
//获得节点node的高度
private int getHeight(Node node){
if(node == null){
return 0 ;
}
return node.height;
}//对节点y进行向右旋转操作，返回旋转后新的根节点x
//yx
/// \向右旋转(y)/\
//xT4------------>zy
/// \/ \/ \
//zT3T1 T2 T3 T4
/// \
//T1T2
private Node rightRotate(Node y){Node x = y.left;
Node T3 = x.right;
//向右旋转过程
x.right = y;
y.left = T3;
//更新height
y.height = Math.max(getHeight(y.left), getHeight(y.right)) + 1;
x.height = Math.max(getHeight(x.left), getHeight(x.right)) + 1;
return x;
}
（2） A的右孩子的右子树插入节点(RR) 如下图所示：插入
节点F后，节点A的平衡因子为-2，对节点A进行左旋操作。
文章图片
图解过程：
文章图片
代码实现：
//RR
if(balanceFactor < -1 && getBalanceFactor(node.right) <= 0){
//新的根节点返回回去，返回给递归调用的上一层
//以这个新的根节点为根的二叉树，就满足了平衡二叉树，又满足了二分搜索树的性质
return leftRotate(node);
}//获得节点node的平衡因子
private int getBalanceFactor(Node node){
if(node == null){
return 0;
}
return getHeight(node.left) - getHeight(node.right);
}
//获得节点node的高度
private int getHeight(Node node){
if(node == null){
return 0 ;
}
return node.height;
}//对节点y进行向左旋转操作，返回旋转后新的根节点x
//yx
/// \向左旋转(y)/\
//T1x------------>yz
/// \/ \/ \
//T2zT1 T2 T3 T4
/// \
//T3 T4
private Node leftRotate(Node y){Node x = y.right;
Node T2 = x.left;
//向左旋转过程
x.left = y;
y.right = T2;
//更新height
y.height = Math.max(getHeight(y.left), getHeight(y.right)) + 1;
x.height = Math.max(getHeight(x.left), getHeight(x.right)) + 1;
return x;
}（3） A的左孩子的右子树插入节点(LR) 若
A的左孩子节点B的右子树E插入节点F，导致节点A失衡。
文章图片
A的平衡因子为2，若仍按照右旋调整，调整过程如下：
文章图片
文章图片
??经过
右旋调整发现，调整后树仍然失衡，说明这种情况单纯的进行右旋操作不能使树重新平衡。那么这种插入方式需要执行两步操作：??（1）对
失衡节点A的左孩子B进行左旋操作，即RR情形操作。??（2）对
失衡节点A做右旋操作，即LL情形操作。图解过程：
文章图片
文章图片
代码实现：
//LR
//左子树比右子树高，高度差比1大，所以是不平衡的
if(balanceFactor > 1 && getBalanceFactor(node.left) < 0){
node.left = leftRotate(node.left);
return rightRotate(node);
}
（4） A的右孩子的左子树插入节点(RL)
右孩子插入左节点的过程与左孩子插入右节点过程类似，只需对右孩子进行LL操作，然后在对节点进行RR操作。图解过程：
文章图片
文章图片
文章图片
代码实现：
//RL
//右子树比左子树高，高度差比小于-1，所以是不平衡的
if(balanceFactor < -1 && getBalanceFactor(node.right) > 0){
node.right = rightRotate(node.right);
return leftRotate(node);
}
3.6 删除
平衡二叉树的删除情况与二叉搜索树删除情况相同，同样分为以下四种情况：??（1）删除
叶子节点??（2）删除节点
只有左子树??（3）删除节点
只有右子树??（4）删除节点
既有左子树又有右子树??
平衡二叉树的节点删除与二叉搜索树删除方法一致，但是需要在节点删除后判断树是否仍然保持平衡，若出现失衡情况，需要进行调整。代码实现：
//删除掉以node为根的二分搜索树中键为key的节点，递归算法
//返回删除节点后新的二分搜索树的根
private Node remove(Node node, K key){
if(node ==null){
return null;
}
Node retNode;
if(key.compareTo(node.key) < 0){
node.left = remove(node.left,key);
retNode = node;
}else if(key.compareTo(node.key) > 0){
node.right = remove(node.right , key);
retNode =node;
}else { //key.compareTo(node.key) == 0
//待删除节点左子树为空的情况
if(node.left == null){
Node rightNode = node.right;
node.right = null;
size -- ;
retNode = rightNode;
}
//待删除节点右子树为空的情况
else if(node.right == null){
Node leftNode = node.left;
node.left = null;
size -- ;
retNode = leftNode;
}else{
//待删除节点左右子树均不为空的情况
//找到比待删除节点大的最小节点，即待删除节点右子树的最小节点
//用这个节点顶替待删除节点的位置
Node successor = minimum(node.right);
successor.right = remove(node.right, successor.key);
successor.left = node.left;
node.left = node.right = null;
retNode = successor;
}
}
if(retNode == null){
return null;
}else{//更新height
retNode.height = 1 + Math.max(getHeight(retNode.left), getHeight(retNode.right));
//计算平衡因子
int balanceFactor = getBalanceFactor(retNode);
//平衡维护
//LL
//不平衡的原因是左侧的左侧多添加了一个节点
if(balanceFactor > 1 && getBalanceFactor(retNode.left) >=0){
//返回递归的上一层，继续处理上一层的节点
//至此，新的根节点，就已经保证了，以这个根节点为根的，
//整棵二叉树即是一个二分搜索树，又是一棵平衡二叉树
return rightRotate(retNode);
}
//RR
if(balanceFactor < -1 && getBalanceFactor(retNode.right) <= 0){
//新的根节点返回回去，返回给递归调用的上一层
//以这个新的根节点为根的二叉树，就满足了平衡二叉树，又满足了二分搜索树的性质
return leftRotate(retNode);
}//LR
//左子树比右子树高，高度差比1大，所以是不平衡的
if(balanceFactor > 1 && getBalanceFactor(retNode.left) < 0){
node.left = leftRotate(retNode.left);
return rightRotate(retNode);
}//RL
if(balanceFactor < -1 && getBalanceFactor(retNode.right) > 0){
node.right = rightRotate(retNode.right);
return leftRotate(retNode);
}return retNode;
}
}
4 结语
平衡二叉树的旋转问题是二叉树学习中的重点与难点，希望读者通过本文可以更好的理解二叉树的操作。推荐阅读 【数据结构|数据结构——平衡二叉树（AVL树）（java版）】数据结构——二叉树基础
推荐阅读
- Java数据结构与算法|Java数据结构与算法（树）——平衡二叉树（AVL树）
- 二叉树|数据结构篇——平衡二叉树（AVL树）
- #|数据结构——平衡二叉树（Java代码实现）
- Java|Java学习——数据结构——AVL树
- Java数据结构|Java数据结构——树——AVL树
- 数据结构|数据结构——平衡二叉树（AVL）
- leetcode|力扣刷题_栈
- 队列|力扣小白刷题之225题用队列实现栈
- java|java 代码高可读性艺术_编写可读性代码的艺术