读书人

AVL兑现

发布时间: 2012-09-06 10:37:01 作者: rapoo

AVL实现
一. AVL概念:
对于一颗BST,其中每个节点的左右子树高度差均不超过1的平衡二叉搜索树,就叫做AVL树。
二. 如何维护一颗AVL树。
旋转操作:
1. rotateWithLeft:(右旋转)
* (N) (L)
* / \ / \
* (L) 3 ==> 1 (N)
* / \ / \
* 1 2 2 3
2. rotateWithRight:(左旋转)
* (N) (R)
* / \ / \
* 1 (R) ==> (N) 3
* / \ / \
* 2 3 1 2

三.AVL的基本操作:


双旋转:


五.实现代码:

读书人网 >编程

热点推荐