🌸个人主页:https://blog.csdn.net/2301_80050796?spm=1000.2115.3001.5343
🏵️热门专栏:
🧊 Java基本语法(97平均质量分)https://blog.csdn.net/2301_80050796/category_12615970.html?spm=1001.2014.3001.5482
🍕 Collection与数据结构 (92平均质量分)https://blog.csdn.net/2301_80050796/category_12621348.html?spm=1001.2014.3001.5482
🧀线程与网络(96平均质量分) https://blog.csdn.net/2301_80050796/category_12643370.html?spm=1001.2014.3001.5482
🍭MySql数据库(93平均质量分)https://blog.csdn.net/2301_80050796/category_12629890.html?spm=1001.2014.3001.5482
🍬算法(97平均质量分)https://blog.csdn.net/2301_80050796/category_12676091.html?spm=1001.2014.3001.5482
🍃 Spring(97平均质量分)https://blog.csdn.net/2301_80050796/category_12724152.html?spm=1001.2014.3001.5482
🎃Redis(97平均质量分)https://blog.csdn.net/2301_80050796/category_12777129.html?spm=1001.2014.3001.5482
🐰RabbitMQ(97平均质量分) https://blog.csdn.net/2301_80050796/category_12792900.html?spm=1001.2014.3001.5482
感谢点赞与关注~~~
目录
1. 二叉搜索树
1.1 概念
二叉搜索树又称为二叉排序树,它可以是一颗空树,或者是具有以下性质的二叉树.
- 若他的右树不为空,则它的右子树上的所有结点都大于根结点.
- 若它的左树不为空,则它的左子树上的所有结点都小于根结点.
- 它的左子树和右子树也分别为二叉搜索树.
1.2 查找结点
如果根节点为空,返回false.如果根结点不为空:
- 如果根结点key == 查找key,返回true.
- 如果根结点key < 查找key,到其右子树中查找.
- 如果根结点key > 查找key,到其左子树中查找.
在查找的时候,我们依然可以和哈希表一样引入相同的概念,ASL,只要涉及到查找的数据结构,都可以引入ASL,即一个元素查找的平均次数,计算公式为需要查找指定元素的次数/需要查找元素的个数,比如上面这张图,我们需要查找1,8,9,可以计算SAL=(3+3+4)/3.
1.3 插入结点
- 如果为空树,直接令root = 所要插入的结点.之后返回true.
- 如果该树不是空树,按照搜索二叉树的性质确定查找逻辑.插入新结点.注意记录cur的父节点,否则无法插入.
二叉搜索树在插入的时候,我们可以看到,它会一直向着子树搜索合适的位置,只有当我们到达一个节点，这个节点没有合适的子节点（即左子节点为空且要插入的值小于当前节点的值，或者右子节点为空且要插入的值大于当前节点的值），这个位置才是符合二叉搜索树性质的插入位置,也就是说二叉搜索树在插入一个结点之后,这个结点一定是叶子结点.
1.4 删除结点(难点)
设待删除的结点是cur,带删除的结点的父节点是parent.
- cur的左子树为空
- 要删除的节点是根结点,直接令root = root.right
- 要删除的结点是中间的结点, 单分支,parent.right = cur.right
- 要删除的结点是中间结点,<字型,parent.left = cur.right
- cur的右子树为空
- 要删除的结点是根结点,直接令root = root.left
- 要删除的结点是中间结点,单分支,parent.left = cur.left
- 要删除的结点是中间结点,>字型,parent.right = cur.left
在删除单分支的时候,也就是要删除的结点左子树和右子树有其中一个为空的时候,直接让他的子节点替代它的位置即可
- cur的左右子树都不为空
可以使用替换法进行删除,即它在右子树中寻找最小的结点,或者在左子树中寻找最大的结点,使用找到的结点替换要删除的结点,然后删除找到的最小(大)的结点,之后又分为两种情况(以右子树为例):- 最小的结点与上下的结点组成<型.
- 最小的结点与上下结点形成单分支.
在删除左子树和右子树都不为空的情况的时候,我们使用替换法来删除所要删除的结点,这个替换的结点,既可以是要删除结点的右子树的最小节点,即遍历右子树的时候遇到没有左子树的节点,这个就是我们想要找到的结点,也可以是要删除结点左子树的最大节点,即遍历左子树的时候,遇到没有右子树的结点,这个结点就是我们想要找到的结点.
[图解]
1.5 实现二叉搜索树
public class SearchBinaryTree {
//搜索树的结点
public static class Node{
public int key;
public Node left;
public Node right;
public Node(int key) {
this.key = key;
}
}
private Node root = null;
/**
* 查找元素
* @param key 索要查找的元素
* @return 返回Node的哈希值
*/
public Node search(int key){
Node cur = root;
while (cur != null){
if (cur.key == key){
return cur;
} else if (cur.key < key) {
cur = cur.right;
}else {
cur = cur.left;
}
}
return null;//没找到,返回null
}
/**
* 在二叉搜索树中插入指定的值
* @param key 所要插入的值
* @return 返回是否插入成功
*/
public boolean insert(int key){
Node node = new Node(key);
Node cur = root;
Node parent = null;//parent用来记录当前节点的父亲节点
if (root == null){
root = node;
return true;
}
while (cur != null){
if (cur.key == key){
return false;//二叉搜索树中不允许有两个相同的值,遇到相等返回false
} else if (cur.key < key) {
parent = cur;
cur = cur.right;
}else {
parent = cur;
cur = cur.left;
}
}
//退出循环后,判断结点应该插入在左侧还是右侧
if (parent.key < key){
parent.right = node;
}else {
parent.left = node;
}
return true;
}
/**
* 删除指定值的结点
* @param key 所要删除的值
* @return 返回是否删除成功
*/
public boolean remove(int key){
Node cur = root;
Node parent = null;
if (root == null){
return false;
}
while (cur != null){
if (cur.key == key){
removeNode(parent,cur);
return true;
} else if (cur.key < key) {
parent = cur;
cur = cur.right;
}else {
parent = cur;
cur = cur.left;
}
}
return false;//没找到,返回false
}
/**
* 找到结点之后删除
* @param parent 父结点
* @param cur 当前要删除的结点
*/
private void removeNode(Node parent,Node cur){
if (cur.left == null){//cur的左结点为空
if (cur == root){//当前要删除的结点是根结点
root = root.right;
} else if (parent.right == cur) {//删除的是单分支的中间节点
parent.right = cur.right;
}else {//删除的是<字型的中间结点
parent.left = cur.right;
}
} else if (cur.right == null) {//cur的右结点为空
if (cur == root){//当前要删除的结点是根结点
root = root.left;
} else if (parent.left == cur) {//删除的是单分支的中间节点
parent.left = cur.left;
}else {//删除的是>字型的中间结点
parent.right = cur.left;
}
}else {//左右结点都不为空,使用替换删除法
//在这个结点的右子树中寻找最小的值,用它进行替换,原因:这样右结点的值一定比替换之后的值大
Node t = cur.right;
Node tparent = cur;
//寻找右子树的最小结点,一直向左子树遍历,因为只有左结点的值才比根结点小,
while (t.left != null){//当没有左结点的时候停止遍历
tparent = t;
t = t.left;
}
cur.key = t.key;
//删除替换掉的结点
if (tparent.left == t){//<字型
tparent.left = t.right;
}else {//单分支型
tparent.right = t.right;
}
}
}
}
我们也可以把既存在左子树,又存在右子树的这种情况替换为从左子树中查找最小元素:
Node t = cur.left;
Node tParent = cur;
//向左子树遍历,寻找右子树为空的节点
while (t.right != null){
tParent = t;
t = t.right;
}
//替换节点
cur.key = t.key;
//删除替换之后的结点
if (tParent.right == t){
tParent.right = t.left;
}else{
tParent.left = t.left;
}
1.6 性能分析
插入和删除操作都必须先查找，查找效率代表了二叉搜索树中各个操作的性能。
对有n个结点的二叉搜索树，若每个元素查找的概率相等，则二叉搜索树平均查找长度是结点在二叉搜索树的深度的函数，即结点越深，则比较次数越多。
但对于同一个关键码集合，如果各关键码插入的次序不同，可能得到不同结构的二叉搜索树：
最优情况下，二叉搜索树为完全二叉树，其平均比较次数为：log2N
最差情况下，二叉搜索树退化为单支树，其平均比较次数为：N/2
1.7 和Java中Collection的关系
TreeMap 和 TreeSet 即 java 中利用搜索树实现的 Map 和 Set；实际上用的是红黑树，而红黑树是一棵近似平衡的二叉搜索树，即在二叉搜索树的基础之上 + 颜色以及红黑树性质验证，关于红黑树的内容后序再进行讲解.
2. AVL树
2.1 概述
我们前面讲的二叉搜索树虽然可以缩短查找效率,但是如果数据接近有序,二叉搜索树将会退化为单分支的树,查找元素相当于在顺序表中查找元素,效率及其低下.所以我们可以引入以下的算法来解决,当二叉搜索树种插入新节点的时候,如果可以保证每个节点的左右子树高度之差的绝对值不超过1,即可降低树的高度,从而减少平均搜索的长度.
一棵AVL树具有以下的性质:
- 空树是AVL树
- 是AVL树,首先需要是一个二叉搜索树.
- 他的左右子树都是AVL树
- 左右高度之差(简称平衡因子)的绝对值不超过1(也就是每个节点的平衡因子只能为-1,0,1).
如果一棵二叉树是高度平衡的,它就是AVL树,如果它有n个结点,其高度可以保持在O(log2N),搜索时间复杂度O(log2N).
2.2 AVL树结点的定义
实现AVL树的时候,我们需要在节点中维护一个该结点的平衡因子,其中当前节点的平衡因子=右子树的高度-左子树的高度,由于在后续会涉及到AVL树的旋转,所以我们需要在节点中维护一个该结点的双亲节点.其他的和二叉树是一样的.
//定义AVL树的结点类
static class Node {
public Node left;//左孩子
public Node right;//右孩子
public Node parent;//双亲
public int bf = 0;//结点的平衡因子
public int val = 0;//结点存放的值
public Node(int val){
this.val = val;
}
}
2.3 AVL树的插入
AVL树就是在二叉搜索树的基础上添加了平衡因子,因此AVL树也可以看做是二叉搜索树.AVL树的插入过程可以分为两步:
- 按照二叉搜索树的方式插入新的结点,cur插入之后,parent的平衡因子一定需要调整,在插入之前,parent的平衡因子分为三种情况:-1,0,1,分一下的两种情况:
- 如果cur插入到了parent的左侧,只需要给parent的平衡因子-1即可
- 如果cur插入到了parent的右侧,只需要给parent的平衡影子+1即可
- 调整结点的平衡因子
- 此时,parent的平衡因子可能会有三种情况:0,±1,±2
- 如果parent的平衡因子为0,说明插入之前parent的平衡因子为±1,插入之后被调整为0此时满足AVL树的性质,插入成功.
- 如果平衡因子为正负1,说明在插入之前,parent的平衡因子为0,插入之后被更新为了±1,此时以parent为根的树的高度增加,需要继续向上更新.
- 如果parent的平衡因子为±2,则parent的平衡因子违反了平衡树的性质,需要对其进行旋转处理.
/**
* 在AVL树中插入结点
* @param val 要插入的值
* @return 返回是否插入成功
*/
public boolean insert(int val){
//首先按照二叉搜索树的方式对结点进行插入
Node node = new Node(val);
if (root == null){
root = node;
return true;
}
Node parent = null;//用来记录当前遍历到的结点的根节点.
Node cur = root;
while (cur != null){//遍历二叉搜索树
if (val == cur.val){
return false;//已经存在该值,插入失败
} else if (val < cur.val) {
parent = cur;
cur = cur.left;
} else {
parent = cur;
cur = cur.right;
}
}
//当cur遍历到null的时候,我们需要插入节点了
if (parent.val < val){
parent.right = node;
}else {
parent.left = node;
}
//在插入结点之后,平衡因子一定会遭到破坏,所以我们需要一直向上调节平衡因子
while (parent != null){
if (node == parent.left){
parent.bf--;//如果插入的Node节点为parent的左,parent的平衡因子--;
}else {
parent.bf++;//相反为--;
}
//查看调整之后的parent的平衡因子为多少
if (parent.bf == 0){
break;//如果平衡因子为0,则已经平衡,不需要在向上调整
} else if (parent.bf == 1) {
cur = parent;
parent = cur.parent;//如果平衡因子为1,则父节点的因子也会遭到破坏,需要继续向上调整平衡因子.
} else {
//平衡因子为2,需要对以parent为根的子树进行旋转处理
if (parent.bf == 2){
//旋转处理,此处先省略,下面补全
}else {
//旋转处理
}
break;//在对parent为根节点的树进行旋转之后,平衡因子为0,对上面的结点没有影响,直接break
}
}
return true;
}
2.4 AVL树的旋转
如果在一课原本是平衡的AVL树中插入一个新的结点,造成了不平衡,此时就必须调节整棵树的结构,使之平衡化.根据插入位置的不同,AVL树的旋转分为四种:
- 新节点插入较高左子树的左侧---->右单旋
在上图插入之前,AVL树是平衡的,新结点插入到30的左子树(注意:此处不是左孩子)中,30左子树增加了一层,导致60为根的二叉树不平衡,要让60平衡,只能将60左子树的高度减少一层,右子树的高度增加一层,即将左子树往上提,将60转下来,因为60比30大,只能将其放在30的右子树,如果30有右子树,右子树的根的值一定大于30小于60,只能将其放在60的左子树,旋转完成之后,更新结点的平衡因子即可.
在旋转的过程中,有以下的情况需要考虑:- 30结点的右孩子可能存在,也可能不存在
- 60可能是根结点,也可能是子树
如果是根结点,旋转完成之后要更新根结点,如果是子树,可能是某个节点的左子树,也可能是右子树.
/**
* 右单旋
* @param parent 结点平衡因子大为2的结点
*/
private void rotateRight(Node parent){
Node subL = parent.left;
Node subLR = subL.right;
parent.left = subLR;
if (subLR != null){//subL的右孩子有可能为空
subLR.parent = parent;
}
subL.right = parent;
Node pParent = parent.parent;//记录当前parent的父节点
parent.parent = subL;//把当前parent的父节点变为subL
if (parent == root){//判断当前要旋转的结点是否是根结点
root = subL;//根结点置为subL
subL.parent = null;//subL的parent置为null
}else {
if (pParent.left == parent){//当前parent是pParent的左孩子
pParent.left = subL;
subL.parent = pParent;
}else {//当前parent是pParent的右孩子
pParent.right = subL;
subL.parent = pParent;
}
}
//调节平衡因子.两个参与旋转的结点的平衡因子都变为了0
subL.bf = 0;
parent.bf = 0;
}
- 新节点插入较高右子树的右侧—>左单旋
原理和右单旋相同,这里不再赘述
/**
* 左单旋
* @param parent 需要旋转的平衡因子为2的结点
*/
private void rotateLeft(Node parent){
Node subR = parent.right;
Node subRL = subR.left;
parent.right = subRL;
if (subRL != null){
subRL.parent = parent;
}
subR.left = parent;
Node pParent = parent.parent;
parent.parent = subR;
if (parent == root){
root = subR;
subR.parent = null;
}else{
if (pParent == parent.left){
pParent.left = subR;
subR.parent = pParent;
}else{
pParent.right = subR;
subR.parent = pParent;
}
}
subR.bf = 0;
parent.bf = 0;
}
- 新节点插入较高左子树的右侧:先左单旋在右单旋(左右双旋)
先对30进行左单旋,进行左单旋之后,再对90进行右单旋.旋转完成之后根据新节点在较高左子树的右侧插入的位置(是插入到了左子树上还是右子树上)去调整平衡因子.
/**
* 进行左单旋之后进行右单旋
* @param parent 平衡因子为2的结点
*/
private void rotateLR(Node parent){
Node subL = parent.left;
Node subLR = parent.right;
int bf = subLR.bf;//记录平衡因子,以便修改平衡因子
rotateLeft(subL);
rotateRight(parent);
if (bf == 1){//按照插入较高左子树的右侧是左子树还是右子树的不同情况调节平衡因子
subL.bf = -1;
subLR.bf = 0;
parent.bf = 0;
}else if (bf == -1){
subL.bf = 0;
parent.bf = 1;
subLR.bf = 0;
}
}
- 新节点插入较高右子树的左侧:先右单旋在左单旋
/**
* 进行右单旋之后进行左单旋
* @param parent 平衡因子为2的结点
*/
private void rotateRL(Node parent){
Node subR = parent.right;
Node subRL = subR.left;
int bf = subRL.bf;
rotateRight(subR);
rotateLeft(parent);
if (bf == 1){
subR.bf = 0;
subRL.bf = 0;
parent.bf = -1;
}else if (bf == -1){
parent.bf = 0;
subR.bf = 1;
subRL.bf = 0;
}
}
总结: 新节点插入之后,假设以parent为根的子树不平衡,即parent的平衡因子为2或者-2,分为一下的情况:
1. parent的平衡因子为2,说明parent的右子树高,设parent的右子树的根为subR
- 当subR的平衡因子为1时,进行左单旋.
- 当subR的平衡因子为-1时,先进行右单旋,再进行左单旋,即左右双旋.
2. parent的平衡因子为-2,说明parent的左子树高,设parent的左子树为subL
- 当subL的平衡因子为-1时,进行右单旋.
- 当subL的平衡因子为1是,先进行左单旋,在进行右单旋,即右左双旋.
即parent与其较高子树节点(sub结点)的平衡因子时同号时单旋转，异号时双旋转.
旋转完成之后,原来的parent为根的子树高度降低,已经平衡,不需要在向上更新.
接下来我们把AVL树插入结点的代码补全:
/**
* 在AVL树中插入结点
* @param val 要插入的值
* @return 返回是否插入成功
*/
public boolean insert(int val){
//首先按照二叉搜索树的方式对结点进行插入
Node node = new Node(val);
if (root == null){
root = node;
return true;
}
Node parent = null;//用来记录当前遍历到的结点的根节点.
Node cur = root;
while (cur != null){//遍历二叉搜索树
if (val == cur.val){
return false;//已经存在该值,插入失败
} else if (val < cur.val) {
parent = cur;
cur = cur.left;
} else {
parent = cur;
cur = cur.right;
}
}
//当cur遍历到null的时候,我们需要插入节点了
if (parent.val < val){
parent.right = node;
}else {
parent.left = node;
}
//在插入结点之后,平衡因子一定会遭到破坏,所以我们需要一直向上调节平衡因子
while (parent != null){
if (node == parent.left){
parent.bf--;//如果插入的Node节点为parent的左,parent的平衡因子--;
}else {
parent.bf++;//相反为--;
}
//查看调整之后的parent的平衡因子为多少
if (parent.bf == 0){
break;//如果平衡因子为0,则已经平衡,不需要在向上调整
} else if (parent.bf == 1) {
cur = parent;
parent = cur.parent;//如果平衡因子为1,则父节点的因子也会遭到破坏,需要继续向上调整平衡因子.
} else {
//平衡因子为2,需要对以parent为根的子树进行旋转处理
if (parent.bf == 2){
//旋转处理
Node subR = parent.right;
if (subR.bf == 1){
rotateLeft(parent);
} else if (subR.bf == -1) {
rotateRL(parent);
}
}else {
//旋转处理
Node subL = parent.left;
if (subL.bf == -1){
rotateRight(parent);
} else if (subL.bf == 1) {
rotateLR(parent);
}
}
break;//在对parent为根节点的树进行旋转之后,平衡因子为0,对上面的结点没有影响,直接break
}
}
return true;
}
2.5 AVL树的验证
AVL树是在二叉搜索树的基础之上加入了平衡性的限制,我们在之前二叉树的OJ专题中曾经验证过平衡树.因此要验证AVL树,可以分为两步:
- 验证其为二叉搜索树:
中序遍历这颗树,只要遍历序列为有序的,就是二叉搜索树. - 验证平衡树
每个节点的高度差都不超过1,如果超过1,返回-1.
public int getHeight2(Node root){
if (root == null){
return 0;//结点为空返回0
}
int leftHeight = getHeight2(root.left);
int rightHeight = getHeight2(root.right);//获取左子树和右子树的高度
if (leftHeight>=0 && rightHeight >=0 && Math.abs(leftHeight-rightHeight)<2 ){
return Math.max(leftHeight,rightHeight)+1;//返回的值不是-1或者是左右树高度差小于2,返回可以获取的高度
}else{
return -1;//如果左树或者右树种有任何一棵树返回-1,或者是高度差大于2,返回-1
}
}
public boolean isBalanced2(Node root) {
if(root == null){
return true;
}
return getHeight(root)>=0;//看root的返回值是否为负数,返回值不为负数,说明平衡,否则不平衡
}
2.6 AVL树性能分析
AVL树是一棵绝对平衡的二叉搜索树，其要求每个节点的左右子树高度差的绝对值都不超过1，这样可以保证查询时高效的时间复杂度，即log2N。但是如果要对AVL树做一些结构修改的操作，性能非常低下，比如：插入时要维护其绝对平衡，旋转的次数比较多，更差的是在删除时，有可能一直要让旋转持续到根的位置。因此：如果需要一种查询高效且有序的数据结构，而且数据的个数为静态的(即不会改变)，可以考虑AVL树，但一个结构经常修改，就不太适合。