联创 Lab 组新人任务第一弹。

关于LLRB

定义

  1. 根节点是黑色的。
  2. 红色节点的儿子一定是黑色的。
  3. 任意节点到任意叶子的最短路径上都有相同数量的黑色节点。
  4. 黑色节点的儿子要么全是黑色，要么只有左儿子是黑色。
  • 前三点与红黑树的性质相同，第四点为左偏红黑树的特殊性质，这导致了它的操作相对红黑树更加简单。
  • 左偏红黑树也可以认为其相邻节点的边是有颜色的。
  • 空节点的颜色认为是黑色。

插入操作

  1. 可以先就像向二叉查找树中插入节点一样操作，插入时将其颜色赋为红色。如果插入时是黑色，这会导致破坏了LLRB的平衡性质。
  2. 保持住了黑色平衡性质之后再来调整其他结构性质，要对连续两个红色节点、只有右儿子是红色节点进行旋转，对左右儿子都是红色的节点进行颜色翻转（拆分2-3-4树中的4-node）。
  3. 其操作可以是递归的，编写代码也将更加容易实现。 优先保持平衡性质的原因有：在一开始插入时保持平衡性质最容易实现（只需要给新节点赋红色），此时若优先考虑其他性质，会导致需要考虑的情况过多，而且在后续进行修补（旋转、颜色翻转）的时候不会破坏其平衡性质。

删除操作

  1. 依然优先考虑其平衡性质，删除的节点需要是红色的，因此思路就是先将需要删除的节点变成红色的。
  2. 此时需要考虑的是，如何将红色节点向下移动（向左下或右下）。当左右儿子都不是红色时也不用担心，可以通过颜色翻转实现，翻转后需要考虑移动的另一个方向是否会出现不满足左倾红黑树的情况，并对其进行修补。
  3. 由于LLRB的左偏特性，因此会出现想要向右下移动时，左儿子是红色而右儿子是黑色，因此需要对该节点进行右旋，让向右下的路径上出现红色。
  4. 当找到删除的目标节点后，如果是一个叶子节点，直接删去，如果是一个内部节点，便从它的右儿子的分支中找到最小节点与之替换，再删掉。
  5. 在向上返回的途中修补节点。

4 中判断是否为叶子节点不应该用它是否有左儿子来判断，而是用它是否有右儿子来判断，因为在前一步中有右旋操作。

实现LLRB

代码文件

https://github.com/vaaandark/MySet

文件结构

  • generator文件夹内有文件generator.c，用于生成测试数据。
  • STLSet文件夹内有文件stl_set.cpp，STL中的Set编写，用于对照实验。
  • src中为基于LLRB Tree的Set的具体实现。
  • 脚本test.sh用于自动化测试，可以使用可选参数clean，用于清理之前测试出现的非代码文件。
  • src_cpp为Set的C++实现。