AVL 树

AVL树的概念

AVL树节点的定义

template<class T>
struct AVLTreeNode
{
 AVLTreeNode(const T& data)
     : _pLeft(nullptr), _pRight(nullptr), _pParent(nullptr)
 , _data(data), _bf(0)
 {}
 AVLTreeNode<T>* _pLeft;   // 该节点的左孩子
 AVLTreeNode<T>* _pRight;  // 该节点的右孩子
 AVLTreeNode<T>* _pParent; // 该节点的双亲
 T _data;
 int _bf;                  // 该节点的平衡因子
};

AVL树的插入

bool Insert(const T& data)
{
    // 1. 先按照二叉搜索树的规则将节点插入到AVL树中
    // ...
    
    // 2. 新节点插入后，AVL树的平衡性可能会遭到破坏，此时就需要更新平衡因子，并检测是否
    //破坏了AVL树的平衡性
    
 /*
 pCur插入后，pParent的平衡因子一定需要调整，在插入之前，pParent
 的平衡因子分为三种情况：-1，0, 1, 分以下两种情况：
  1. 如果pCur插入到pParent的左侧，只需给pParent的平衡因子-1即可
  2. 如果pCur插入到pParent的右侧，只需给pParent的平衡因子+1即可
  
 此时：pParent的平衡因子可能有三种情况：0，正负1， 正负2
  1. 如果pParent的平衡因子为0，说明插入之前pParent的平衡因子为正负1，插入后被调整
成0，此时子树的高度没有变化，所以无需继续往上调整
  2. 如果pParent的平衡因子为正负1，说明插入前pParent的平衡因子一定为0，插入后被更
新成正负1，此时该子树的高度增加，所以需要往上继续调整
  3. 如果pParent的平衡因子为正负2，则pParent的平衡因子违反平衡树的性质，需要对其进
行旋转处理
 */

 while (pParent)
 {
        // 更新双亲的平衡因子
     if (pCur == pParent->_pLeft)
         pParent->_bf--;
     else
         pParent->_bf++;
     // 更新后检测双亲的平衡因子
     if (0 == pParent->_bf)
     {    
            break;
     }
     else if (1 == pParent->_bf || -1 == pParent->_bf)
     {
              // 插入前父节点的平衡因子是0，插入后父节点的平衡因为为1 或者 -1 ，说明以父节点
    为根的二叉树的高度增加了一层，因此需要继续向上调整
         pCur = pParent;
         pParent = pCur->_pParent;
     }
     else
     {
     // 双亲的平衡因子为正负2，违反了AVL树的平衡性，需要对以pParent为根的树进行旋转处理
      f(2 == pParent->_bf)
      {
              // ...
      }
      else
      {
              // ...
       }

  }


  return true;
}

AVL树的旋转

parent平衡因子为-2：

为-2说明parent左边高，那就找到parent左孩子节点subL，假如subL的平衡因子为-1，说明还是左边高，那就一个parent的右旋即可

假如subL的平衡因子为1，那就说明右边高，这里subLR的平衡因子会影响最后parent和subL的平衡因子，却不会影响旋转的方式

注意：

1、所谓双旋，起始就是两次单旋而已

2、假如只需要一次单旋，那么会涉及两个节点的平衡因子的改变，且这两个节点平衡因子最后都会是0

3、假如需要两次旋转，会涉及到三个节点，其中会有两个节点的平衡因子最后是0，另一个节点平衡因子根据subLR或subRL一开始的平衡因子来决定

4、一次单旋中，会涉及到四个节点，其中有两个节点都可能为空（最上面和最下面），最终需要调整的指针个数是4~6，两个不可能为空的节点各有两个指针需要调整，那两个可以为空的节点每有一个不为空，那就会多一个需要调整的指针

parent的平衡因子为2：

仿照为-2的思路即可

AVL树的验证

AVL树是在二叉搜索树的基础上添加了平衡因子的设置，所以AVL树的验证分为两步，一个是二叉搜索树性质的验证，另一个是平衡树性质的验证

1、对搜索树性质的验证看中序是不是有序的

2、对平衡树性质的验证检查每个节点的平衡因子绝对值不超过1即可

AVL树的模拟实现

AVL树模拟

红黑树

红黑树的概念

红黑树是在搜索树的基础上添加了颜色规则，对于一颗红黑树，要么该树是一颗空树，要么该树的根节点是黑，每条路径上都有相同数量的黑色节点，且不能有相邻的红色节点

红黑树不像AVL树一样保证绝对的平衡，而是保证该树的最长路径不会超过最短路径的二倍，保证的是相对的平衡，这样放宽条件可大大减少旋转次数提高效率

为什么最长路径不超过最短路径的二倍？

每条路径上的黑色节点个数相同，不能有相邻的红色节点，所以最长路径就是红色间隔黑色，而最短路径就是只有黑色，所以最长路径是最短路径的二倍

红黑树节点的定义

// 节点的颜色
enum Color{RED, BLACK};
// 红黑树节点的定义
template<class ValueType>
struct RBTreeNode
{
 RBTreeNode(const ValueType& data = ValueType()，Color color = RED)
     : _pLeft(nullptr), _pRight(nullptr), _pParent(nullptr)
     , _data(data), _color(color)
 {}
 RBTreeNode<ValueType>* _pLeft;   // 节点的左孩子
 RBTreeNode<ValueType>* _pRight;  // 节点的右孩子
 RBTreeNode<ValueType>* _pParent; // 节点的双亲(红黑树需要旋转，为了实现简单给
出该字段)
 ValueType _data;            // 节点的值域
 Color _color;               // 节点的颜色
};

注意：红黑树节点的默认构造我们给的是红色，因为如果插入黑色节点，那么一定会破坏每条路径有相同数量黑色节点的规则，而如果插入红色节点则不一定破坏

红黑树的插入操作

插入红色新节点cur，如果parent是黑色，那就不用调整

如果parent是红色，那就得调整，因为红黑树的根节点是黑色，所以parent肯定不是根节点，不是根节点那parent的父节点肯定存在，因为不能有相邻红色节点，所以grandfa一定是黑色，这时我们要根据叔叔节点来判断调整策略，我们需要先判断parent是grandfa的哪个孩子，然后就能得到叔叔节点了

1、叔叔节点存在且为红色

只需要将parent和uncle变为黑色，grandfa变为红色，grandfa子树每条路径的黑色节点个数不变，但需要往上继续调整，因为变红的granfa很有可能会再次导致有相邻的红色节点

cur是parent的左孩子还是右孩子不重要，因为调整策略是给parent和uncle变色，根本就没有旋转

2、叔叔节点不存在或叔叔节点存在且为黑色

这时cur是parent的左孩子还是右孩子是有关系的，因为这时必须涉及旋转

假如parent是左孩子，cur也是左孩子，那这时就grandfa右旋，右边的路径黑色节点个数不变，左边的黑色节点个数减1，然后grandfa变色，右边路径的黑色节点个数也减1，然后parent再变成黑色，所有路径黑色节点个数加一，和之前一样，并且此时不再需要往上继续调整了，因为parent是子树的根且是黑色

假如parent是左孩子，cur是右孩子，那这时单单一个右旋加变色就不行了，因为最后cur和grandfa都是红色，还是不合规则，所以要进行两次旋转，先对parent左旋，然后对grandfa右旋，最后将grandfa和变成红，cur变成黑

红黑树的验证

红黑树是在二叉搜索树的基础上添加了颜色规则，所以要验证的有四点，中序是否有序来检验是不是搜索树，根节点是否为黑、是否不存在相邻的红色节点、每条路径上黑色节点个数是否相同三点保证是平衡树，如果都满足就是红黑树

红黑树与AVL树的比较