《编程珠玑,字字珠玑》读书笔记完结篇——AVL树
写在最前面的 手贱翻开了《珠玑》的最后几章,所以这一篇更多是关于13、14、15章的内容。这篇文章的主要内容是“AVL树”,即平衡树,比红黑树低一个等次。捣乱真惹不起红黑树,情况很复杂;而AVL思路比较清晰。《编程珠玑,字字珠玑》910读书笔记——代码优化更新了,做了点关于“哨兵”的笔记。在这篇文章的末尾,笔者还加了对引用调用的“大彻大悟”。 4篇读书笔记:全在这里 AVL树 学习数据结构的时候,有过一次实验课, 题意大概:英文单词出现次数统计。当时选了哈希表,映射(map),AVL树(平衡树)三种方法来做,是冲着“完成实验老师请吃饭”去做的。哈希表键值用“除留余数法”,处理冲突用了最简单的开哈希表的“链地址法”。映射(map)没有深入,只是简单的应用。比较痛心的是AVL树。 AVL树的旋转 树的旋转分四种:左单旋,右单旋,左右旋转,右左旋转。规定,右子树的高度减去左子树的高度得到此节点的平衡数(也叫平衡因子,balance factor,bf),用bf(node)表示node节点的平衡数。小剖一下这四种情况: 当bf(node)==2的时候,即右子树高度比左子树高,需要将树在node...