判断是否是AVL树

上一篇文章我们详细介绍了AVL树并且实现了AVL树，这篇文章我们将在前言中引入判断是否是AVL树的方法，然后我们就进入红黑树的实现，如果是能自己实现AVL树的同学那么实现起红黑树就会非常简单了，下面我们介绍一下如何判断AVL树：

首先AVL树本质是根据平衡因子的调节来实现平衡，所以我们可以根据平衡因子来判断，代码如下：

        bool IsBalance()
    {
      return _IsBalance(_root);
    }

int _Height(Node* root)
    {
      if (root == nullptr)
      {
        return 0;
      }
      return _Height(root->_left) > _Height(root->_right) ? _Height(root->_left) + 1 : _Height(root->_right) + 1;
    }

bool _IsBalance(Node* root)
    {
      if (root == nullptr)
      {
        return true;
      }
      int left = _Height(root->_left);
      int right = _Height(root->_right);
      if (abs(right - left) >= 2)
      {
        cout << root->_kv.first << "节点的高度差大于等于2" << endl;
        return false;
      }
      if (right - left != root->_bf)
      {
        cout << root->_kv.first << "节点的平衡因子错误" << endl;
        return false;
      }
      return _IsBalance(root->_left) && _IsBalance(root->_right);
    }

如上代码所示，我们先写了一个求树高度的函数，因为等会要判断每个节点的左右高度差，然后我们先求出整棵树的左右子树的高度，然后判断左右子树高度差是否小于2，如果不小于则说明不是AVL树，然后再判断平衡因子，平衡因子是等于右子树高度减去左子树高度，如果右树高度减去左树高度不等于平衡因子大小则说明平衡因子错了也不是AVL树，然后我们再分别判断每颗子树即可。下面我们跑一下测试：

void test1()
{
  /*int a[] = { 16,3,7,11,9,26,18,14,15 };*/
  int a[] = { 4,2,6,1,3,5,15,7,16,14 };
  AVLTree::AVLTree<int, int> at;
  for (auto& e : a)
  {
    //打条件断点
    /*if (e == 14)
    {
      int x = 0;
    }*/
    at.insert(make_pair(e, e));
    cout << e << "插入：" << at.IsBalance() << endl;
  }
  at.Inorder();
  cout << endl;
  cout << at.IsBalance() << endl;
}

上面条件断点的方式大家可以学一下，当数据量很多需要调试的时候，比如上图中的数据只有插入14的时候才会引发旋转，所以我们可以单独在14这个节点测一下旋转是否正确，只需要写个if语句然后在语句中随便写一个代码，因为如果语句为空是打不上断点的，如下图：

下面在跑一下随机数测试：

void test2()
{
  srand(time(0));
  const size_t N = 100000;
  AVLTree::AVLTree<int, int> at;
  for (size_t i = 0; i < N; i++)
  {
    size_t x = rand();
    at.insert(make_pair(x, x));
  }
  cout << at.IsBalance() << endl;
}

可以看到也是没有问题的，以上AVL树就结束了，下面我们就开始红黑树的学习。

一、红黑树

红黑树，是一种二叉搜索树，但在每个结点上增加一个存储位表示结点的颜色，可以是Red或Black。 通过对任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路径会比其他路径长出俩倍，因而是接近平衡的。

如下图所示：

红黑树的性质：

1. 每个结点不是红色就是黑色。

2. 根节点是黑色的。

3. 如果一个节点是红色的，则它的两个孩子结点是黑色的。

4. 对于每个结点，从该结点到其所有后代叶结点的简单路径上，均包含相同数目的黑色结点。

5. 每个叶子结点都是黑色的 ( 此处的叶子结点指的是空结点 )。

我们在实现的时候，对于新增节点来说我们是新增红色的还是黑色呢？如果是红色则会违反规则3，如果是黑色则会违反规则4，在这里我们一定要注意，违反规则3是有几率的，如果我们新增节点的父亲是黑色那就不会违反规则3，但是如果新增节点是黑色那么这条路径一定会多一条黑色这样就一定破坏规则4，所以我们的新增节点的颜色一定是红色。

黑树实现比较简单，所以实际运用中红黑树更多。