纪梵希网站设计分析_ui界面图标_友情链接软件_谷歌浏览器 安卓下载

AVL树的概念

->一棵AVL树可能为空树，或者是具有如下性质的二叉搜素树
->它的左右子树都是AVL树
->左右子树高度之差(平衡因子)的绝对值不超过1(即其值为-1/0/1)

说明：
如果一棵二叉搜索树是平衡的，它就是AVL树，如果它有n个节点，其高度会保持在log2(n)，搜索时间复杂度为O(log2(n))

AVL树节点的定义

1.指向左孩子的指针

2.指向右孩子的指针

3.指向双亲的指针

4.存放数据的节点

5.平衡因子

AVL树的插入

步骤

1.按照二叉搜索树的插入方式插入新节点

2.调整各个节点的平衡因子

分类

在插入之前，插入的树是一棵AVL树，所以pParent的平衡因子分为三种情况，-1，0，1

插入pParent的左子树，pParent的平衡因子需要-1

插入pParent的右子树，pParent的平衡因子需要+1

插入并调整pParent的平衡因子后，会有三种情况

1.pParent的平衡因子为0，说明之前pParent的平衡因子为正负1，插入后被调整为0，满足AVL树的性质，插入成功

2.pParent的平衡因子为正负1，说明插入之前pParent的平衡因子的值一定为0，插入后被更新成了正负1，所以以pParent为根的树高度增加，需要继续向上更新

3.pParent的平衡因子成为了正负2，说明pParent的平衡因子违反了AVL树的性质，需要对其进行旋转处理

AVL树的旋转

1.新节点插入到较高左子树的左侧，左左，进行右单旋

2.新节点插入到较高右子树的右侧，右右，进行左单旋

3.新节点插入到较高左子树的右侧，左右，先进行左单旋，再进行右单旋

4.新节点插入到较高右子树的左侧，右左，先进行右单旋，再进行左单旋

在代码实现层面

假如以pParent为根的子树不平衡，即pParent的平衡因子为正负2

1.pParent的平衡因子为2，说明pParent的右子树高，设pParent的右子树根为pSubR

->当pSubR的平衡因子为1时，进行左单旋

->当pSubR的平衡因子为-1时，进行右左双旋

2.pParent的平衡因子为-2，说明pParent的左子树高，设pParent的左子树根为pSubL

->当pSubL的平衡因子为-1，进行右单旋

->当pSubL的平衡因子为1，进行左右双旋

在旋转完成以后，原pParent为根的树的平衡因子已经满足AVL树的性质，不需要再向上更新

AVL树的验证

1.验证其为二叉搜索树

如果进行中序遍历得到一个有序序列，那么其就是一个二叉搜索树

2.验证其平衡树

满足以下两个条件

->每个子树绝对值的高度差不超过1

->每个节点的平衡因子计算要正确

AVL树的删除

略

AVL树的性能

由于AVL树左右节点的高度差不超过1，在查询时能保证高效的的时间复杂度，即log2(N)，但进行修改操作时，效率就非常低下