第二堂数据结构课：AVL还没捂热，红黑树就来了

第二堂数据结构课AVL还没捂热红黑树就来了上节课刚把AVL的四种旋转理清楚这节课老师直接抛出红黑树说“AVL太严格了旋转太频繁生产环境里其实用红黑树更多”。我当时内心不过听完两节课发现这些东西其实是层层递进的从“严格平衡”到“近似平衡”从内存数据结构到磁盘数据结构。整理一下今天的笔记。AVL的严格与代价上节课讲了AVL的旋转机制这节课老师补充了构建过程和它的局限性。插入节点后要从插入位置开始一路向上检测父节点的平衡因子一旦发现哪个节点的左右子树高度差超过1就要立刻旋转。LL、RR、LR、RL四种情况各有一套对应的旋转组合。AVL的优点是查询快——严格平衡保证了树高维持在O(logN)级别。但代价也很明显每次插入删除都可能触发多次旋转维护成本高。老师说它的典型场景是查询多、增删少比如一些只读的配置数据。但现实中哪有那么多只查不改的业务所以红黑树来了。红黑树没那么严格但够用说实话红黑树这部分我听得有点懵课后查了不少资料才勉强串起来。老师用一种很巧妙的方式讲红黑树——先讲2-3-4树再说红黑树是它的等价表示。2-3-4树就是节点可以容纳1到3个键值分别对应2节点、3节点、4节点。红黑树的本质就是用“颜色”来表示一个节点到底是单独的节点还是和其他节点合并在一起的。2节点 → 一个黑色节点3节点 → 黑节点带一个红色子节点“黑-红”或“红-黑”4节点 → 黑节点带两个红色子节点“黑-红-红”数据永远插在叶子节点如果节点溢出比如4节点再插入就变5节点就把中间值上提给父节点自己分裂成两个2节点。红黑树有五个性质老师让背的根节点是黑的红色节点不能相邻所有叶子节点Nil是黑的从任意节点到叶子经过的黑节点数量相同新插入的节点默认是红的这些约束保证了最坏情况下最长路径不会超过最短纯黑路径的两倍所以查找、插入、删除仍然是O(logN)。和AVL比红黑树的平衡没那么严格但插入删除的旋转次数少很多所以实际工程中更常用。老师说Java的TreeMap、C的std::map底层都是红黑树。哈夫曼树从树到压缩算法这部分是今天感觉最“实用”的因为它直接讲数据压缩。哈夫曼树的构建是一个贪心过程给一组带权值的叶子节点每次选两个权值最小的合并成一棵新树新节点的权值是两者之和重复直到只剩一棵树。这样权值大的节点离根近权值小的离根远整棵树的带权路径长度WPL最小。构建完成后左路径标0右路径标1每个字符就得到一个唯一的二进制编码。关键特性是任何字符的编码都不是其他字符编码的前缀——这叫前缀编码。解码的时候从左往右读读到哪个字符就是哪个不需要分隔符不会产生歧义。老师举了个例子比如A、B、C、D四个字母频率分别是50、25、15、10用哈夫曼编码压缩率很高。反过来如果用固定长度编码每个字符都得占2位浪费空间。栈和队列两个老朋友这部分内容相对简单老师快速过了一遍。栈先进后出Push和Pop都是O(1)。函数调用栈、浏览器的后退、表达式求值都靠它。队列先进先出Enqueue和Dequeue也是O(1)。消息队列、打印机任务调度、BFS遍历都用队列。属于基础中的基础但几乎无处不在。B树磁盘时代的产物B树是今天收尾的内容也是理解成本最高的一块。传统BST一个节点只存一个键值树的高度取决于数据量。数据量一大树就高查找就要访问很多节点。这在内存里没问题但一旦数据存在磁盘上问题就来了——磁盘I/O是机械寻道慢得离谱。B树的核心思路是一个节点多存几个键值多挂几个子节点。比如一棵4阶B树每个节点最多3个键值、4个子节点存100万条数据树高也就3到4层。查找一个数据最多访问3到4个节点也就是3到4次磁盘I/O。而BST可能要20多次。B树的节点大小通常设计成和磁盘页Page大小一致约4KB这样一次I/O就能把整个节点数据全读进来充分利用磁盘顺序读的特性。文件系统和数据库索引比如MySQL的B树底层都是B树及其变体。这部分老师只是引了个头说后续课程会细讲。这节课的几点感受信息密度比第一节课还大尤其是红黑树和B树课上听一遍肯定不够课后得自己再消化。我目前的计划是把红黑树的五种性质和234树的转换关系再推一遍找一道哈夫曼编码的题亲手算一遍走通整个流程B树暂时先理解核心思想和应用场景细节等后续课程跟进老师说数据结构的终极目标是“在合适的地方用合适的结构”目前我的状态还是“能认出这些结构长什么样”离“知道什么时候用”还有距离。继续加油吧。