RB-Tree

C++红黑树实现

包括插入、修正、删除(未实现)等操作

数据结构

• RBNode
  • RBNode*left
  • RBNode*right
  • RBNode*parent
  • int val
  • bool color（default 1）//red 1 black 0
  • RBNode()
  • ~RBNode()

类

• class RBTree
  • 成员属性 RBNode*root
  • public 成员函数 void Insert(T val); void Fix(RBNode* cur); void Delete(); void erase();
  • RBTree()
  • ~RBTree()
  • private 成员函数 void L_Rotate(); void R_Rotate();

错误记录

• 将模板类在头文件中实现，不然会编译报错
• 关于红黑树插入修复操作，参考网上的博客，发现很多都不完整，导致测试样例（1-10）失败。
• 这里给出红黑树插入修复操作的完整思路：
  • 插入节点为根节点时，设置该节点为根节点，将其涂为黑色
  • 插入节点的父节点为红色时，分为两种大情况：1、叔节点为红色 2、叔节点为黑色
    • 1、叔节点为红色时，进行变色，父亲和叔叔变黑，祖父变红，将当前节点设为祖父
    • 2、叔节点为黑色时，根据当前节点与父节点的位置分成四种情况讨论：
      • 当前节点在左子树，父节点为左节点（左左）：把祖父节点设为当前节点，并涂红色，父节点涂黑色，右旋
      • 当前节点在左子树，父节点为右节点（左右）：以父节点为当前节点，左旋，然后变成情况1
      • 当前节点在右子树，父节点在左节点（右左）：以父节点设置为当前节点，右旋，然后变成情况3
      • 当前节点在右子树，父节点在右节点（右右）：把祖父节点涂为红色，并设置为当前节点，父节点涂为黑色，左旋