好记性不如铅笔头

C && C++, C++ STL, 编程

C++ STL读书笔记:平衡二叉树AVL Tree

备注:

本读书笔记基于侯捷先生的《STL源码剖析》,截图和注释版权均属于原作者所有。
本读书笔记中的源码部分直接拷贝自SGI-STL,部分代码删除了头部的版权注释,但代码版权属于原作者。
小弟初看stl,很多代码都不是太懂,注释可能有很多错误,还请路过的各位大牛多多给予指导。
为了降低学习难度,作者这里换到了SGI-STL-2.91.57的源码来学习,代码下载地址为【 http://jjhou.boolan.com/jjwbooks-tass.htm 】

其他网站【 http://www.cnblogs.com/abatei/archive/2008/11/17/1335031.html 】

二叉搜索树是具有下列性质的二叉树:

若它的左子树不空,则左子树上所有结点的值均小于它的根结点的值。
若它的右子树不空,则右子树上所有结点的值均大于它的根结点的值。
它的左、右子树也分别为二叉排序树。

二叉搜索树的插入和删除图解:

平衡二叉树AVL Tree是具有下列性质的二叉搜索树:

AVL树中的每个结点都有一个平衡因子(balance factor,以下用BF表示),它表示这个结点的左、右子树的高度差,也就是左子树的高度减去右子树的高度的结果值。AVL树上所有结点的BF值只能是-1、0、1。反之,只要二叉树上一个结点的BF的绝对值大于1,则该二叉树就不是平衡二叉树。

平衡二叉树AVL Tree图解:


外侧插入,单旋转如下图:


自己画的图:

内侧插入,双旋转如下图:

自己画的图:

删除和代码实现以后笔记吧。

发表评论

3 × 2 =

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据