AVL树是二叉查找树的升级版,他对二叉查找树的节点重新分配布局,降低的搜索数据的时间
AVL树:在AVL树中任何节点的两个子树的高度最大差别为1,所以它也被称为高度平衡树
其核心操作是左旋和右旋操作
右旋
1 | void turnright(node* &root)//右旋操作 |
左旋
1 | void turnleft(node* &root)//左旋操作 |
插入操作
插入操作包括两个步骤,一个是插入,另一个是平衡,平衡是递归回溯的时候完成的。
需要平衡的条件是当一个结点的平衡因子的结点为2,因为平衡树的平衡因子的绝对值最大就是1,当我们插入一个结点的时候,将会导致一个结点的值为2。所以当结点的平衡因子为2时,他的子节点平衡因子为1时就是需要平衡的时候
有一下几种情况
LL型
LR型
RL型
RR型
1 | void insert(node* &root,int x)//插入结点 |
创建结点
1 | node* newnode(int x)//创建结点 |
获取结点高度
1 | int getheight(node* root)//得到结点的高度 |
更新结点高度
1 | void updateheight(node *root)//更新结点的高度 |
计算平衡因子
1 | int getfactor(node* root)//计算平衡因子 |
整体代码
1 | #include <iostream> |
本文作者: jiangyuhao
本文链接: http://example.com/2022/06/11/AVL%E6%A0%91/
版权声明: 本作品采用 知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议 进行许可。转载请注明出处!