AVL Tree Revalent-Codeplayer-ChinaUnix博客

文章分类

文章存档

2011年（26）

2010年（92）

我的朋友

相关博文

AVL Tree Revalent

分类： C/C++

2011-10-19 13:40:56

AVL树的平衡化处理

在一棵AVL树上插入结点可能会破坏树的平衡性，需要平衡化处理恢复平衡，且保持BST的结构性质。

若用Y表示新插入的结点，A表示离新插入结点Y最近的，且平衡因子变为±2的祖先结点。

可以用4种旋转进行平衡化处理:

①LL型：新结点Y 被插入到A 的左子树的左子树上（顺）

②RR型：新结点Y 被插入到A 的右子树的右子树上（逆）

③LR型：新结点Y 被插入到A 的左子树的右子树上（逆、顺）

④RL型：新结点Y 被插入到A 的右子树的左子树上（顺、逆）

阅读(1284) | 评论(0) | 转发(0) |

下一篇：Xen

给主人留下些什么吧！~~

感谢所有关心和支持过ChinaUnix的朋友们