林子er_个人页

2023年07月

• 07.24 09:08:27
  发表了文章 2023-07-24 09:08:27

  红黑树是怎么来的

  本文从二叉搜索树倾斜的原因（自上而下生长）出发，推出维持树形数据结构平衡性的关键：自下而上裂变式生长，进而引出裂变式生长的理论模型：2-3 树。由于 2-3 树实现上的复杂性，引出其实现上的替代品：红黑树。最后，我们讨论如何通过左旋、右旋以及颜色翻转这“三板斧”来维护红黑树插入和删除元素后的动态平衡。