文章目录
-
- 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 代码高可读性艺术_编写可读性代码的艺术