文章
红黑树:规则、旋转与染色
从五条规则、插入染色、旋转和 2-3-4 树视角理解红黑树的近似平衡。
NOTES / THINKING IN PUBLIC
记录技术实践,也记录判断如何形成、结论在什么条件下成立。
从五条规则、插入染色、旋转和 2-3-4 树视角理解红黑树的近似平衡。
通过下一个更大元素和滑动窗口最大值理解单调结构,说明为什么每个元素最多进出一次。
理解 2-节点、3-节点、向上分裂与绝对平衡,并建立通往红黑树和 B 树的桥梁。
用归并排序、快速排序和递归树理解分治的拆分、求解、合并三步,以及复杂度如何分析。
围绕平衡因子、LL/RR/LR/RL 旋转、高度更新和不变量测试理解严格平衡树。
用区间调度、跳跃游戏和分发糖果理解贪心策略,重点说明为什么贪心必须证明正确性。
掌握 BST 有序不变量、三类删除情况、树高复杂度以及有序输入导致的退化问题。
从 BFS、DFS、拓扑排序、Dijkstra、Bellman-Ford、Floyd 和最小生成树建立图算法选择路线。
从字符路径、结束标记与节点表示理解前缀检索,并补充 Unicode 与压缩 Trie 边界。
串联暴力匹配、Rabin-Karp、KMP、Trie、AC 自动机、回文和字符串哈希,建立字符串算法路线。
利用完全二叉树和数组索引理解上浮、下沉、建堆、Top K 与优先队列。
从斐波那契、打家劫舍、背包和子序列问题理解 DP 的状态、选择、转移、base case 与遍历顺序。