AVL tree rotate
2024-10-21 18:30:26
AVL tree
single rotate
/**
* Rotate binary tree node with left child.
* For AVL trees, this is a single rotation for case 1.
* Update heights, then set new root.
*/
void rotateWithLeftChild( AvlNode * & k2 )
{
AvlNode *k1 = k2->left;
k2->left = k1->right;
k1->right = k2;
k2->height = max( height( k2->left ), height( k2->right ) ) + 1;
k1->height = max( height( k1->left ), k2->height ) + 1;
k2 = k1;
}
k2
/ \
k1 z
/ \
x y
|
k1
/ \
x k2
| / \
y z
/**
* Rotate binary tree node with right child.
* For AVL trees, this is a single rotation for case 4.
* Update heights, then set new root.
*/
void rotateWithRightChild( AvlNode * & k1 )
{
AvlNode *k2 = k1->right;
k1->right = k2->left;
k2->left = k1;
k1->height = max( height( k1->left ), height( k1->right ) ) + 1;
k2->height = max( height( k2->right ), k1->height ) + 1;
k1 = k2;
}
k1
/ \
X k2
/ \
y z
|
-->
k2
/ \
k1 z
/ \ |
x y
doublerotate
/**
* Double rotate binary tree node: first left child.
* with its right child; then node k3 with new left child.
* For AVL trees, this is a double rotation for case 2.
* Update heights, then set new root.
*/
void doubleWithLeftChild( AvlNode * & k3 )
{
rotateWithRightChild( k3->left );
rotateWithLeftChild( k3 );
}
k3
/ \
k1 d
/ \
a k2
/ \
b c
-->
k2
/ \
k1 k3
/ \ / \
a b c d
/**
* Double rotate binary tree node: first right child.
* with its left child; then node k1 with new right child.
* For AVL trees, this is a double rotation for case 3.
* Update heights, then set new root.
*/
void doubleWithRightChild( AvlNode * & k1 )
{
rotateWithLeftChild( k1->right );
rotateWithRightChild( k1 );
}
k1
/ \
a k3
/ \
k2 d
/ \
b c
-->
k2
/ \
k1 k3
/ \ / \
a b c d
最新文章
- JQuery 方法简写
- php 无限循环
- 云主机上搭建squid3代理服务器
- MVC 5 的 EF6 Code First 入门
- WebService学习整理（一）——客户端三种调用方式整理
- 翻译-你必须知道的28个HTML5特征、窍门和技术
- Android软件盘InputMethodManager
- [ML]机器学习书单
- Java面试2018常考题目汇总
- 华莱士的 第一个python程序之（用户登录）
- java添加菜单项目
- listView item分割线不显示
- python set和get实现
- 关于百度world 编辑器改变上传图片的保存路径图片不显示的问题
- js回车、ESC、F2按钮事件
- ==和Equals与值类型和引用类型
- KEUC首次落地中国，网易云深度剖析Kubernetes优化与实践
- Spring Cloud和Dubbo整合开发笔记(1)
- JFinal record类型数据在前台获取
- CentOS 6 系统启动流程