1、二叉搜索树

1-1、概念

1-2 二叉搜索树的增、删、查

1-2-1 二叉搜索树的增加（结点数据）

1-2-2二叉搜索树的查找

1-2-3 二叉搜索树的删除

1-2-4 二叉搜索树的性能分析

2、AVLTree

2-1 AVLTree的概念

2-1-1 左单旋：

2-1-2 右单旋：

2-1-3 左右单旋：

2-2 总结：

3、红黑树

3-1 红黑树的概念：

3-2 红黑树的性质：

3-3 红黑树的调整

3-3-1 第一种情况：叔叔为红。

3-3-2 第二种情况：叔叔为黑色或者叔叔不存在

3-3-3 针对叔叔为红或者叔叔不存的情况，还有一种可能，即新增结点位于p2的右孩子处。（情况三）

3-4 红黑树与AVL树的比较

3-5 红黑树的应用

1、二叉搜索树

我们之所以将其放在这里来讲，最主要的原因就是之前我们所有模拟实现都是用C去实现的，而这些东西用C语言很难实现，所以，我们将其放在C++当中。

1-1、概念

二叉搜索树又称二叉排序树，它要么是一个空树，要么是满足以下性质的一个二叉树。

若它的左子树不为空，则左子树上所有节点的值都小于根节点的值

若它的右子树不为空，则右子树上所有节点的值都大于根节点的值

它的左右子树也分别为二叉搜索树

就像下面这棵树一样：

1-2 二叉搜索树的增、删、查

1-2-1 二叉搜索树的增加（结点数据）

假设我们已经有了这么一棵二叉搜索树A，那么我现在要增加一个结点key，遵循以下原则：

①如果原来的树A为空，那就直接插入。

②如果原来的树A不为空，按照二叉树的性质寻找插入位置：从根结点开始，如果比根结点的数据大，那就继续在根结点的右子树中去寻找；如果比根节点的数据小，那就继续在根结点的左子树中去寻找。

③直至找到空（指针）为止。

④插入结点。

我们举一个例子：

就比如上图的那个二叉搜索树，我们要插入元素12，按照步骤来：

①树A不为空树。

②12比5大，继续往其（根结点5的）右子树中寻找；12比7大，继续往其（结点7的）右子树中寻找；12比8大，继续往其（结点8的）右子树中寻找；12比9大，继续往其（结点9的）右子树中寻找。

③此时我们发现，9的右子树为空，停止寻找。

④插入新结点12。

动图我就不做了，就看文字描述吧，已经说得很清楚了。而且这个点也比较简单。

1-2-2二叉搜索树的查找

与增加结点类似，查找也是同样的道理。

从根结点开始，如果根结点比目标结点的数值（key值）大，那么就往其左子树找，反之则往其右子树找。直到找到目标的数为止。找到则返回true，否则返回false。

通过我们下面的代码也可以很清晰地看出这一过程。

1-2-3 二叉搜索树的删除

首先查找元素是否在二叉搜索树中，如果不存在，则返回, 否则要删除的结点可能分下面四种情况：

a. 要删除的结点无孩子结点

b. 要删除的结点只有左孩子结点

c. 要删除的结点只有右孩子结点

d. 要删除的结点有左、右孩子结点

看起来有待删除节点有4中情况，实际情况a可以与情况b或者c合并起来，因此真正的删除过程如下：

情况b：删除该结点且使被删除节点的双亲结点指向被删除节点的左孩子结点

情况c：删除该结点且使被删除节点的双亲结点指向被删除结点的右孩子结点

情况d：在它的右子树中寻找中序下的第一个结点(关键码最小)，用它的值填补到被删除节点中，再来处理该结点的删除问题

什么叫关键码最小？

简而言之，就是在其右子树中找到一个最小的数然后和它替换（也可以在左子树中找到一个最大的数来进行替换），我们下面的例子都是采用右子树中找到一个最小的数然后和它进行替换。

看起来这很复杂，但是与下面的AVL树的旋转相比，这就是小菜一碟。

不过删除的操作也确实是二叉搜索树中比较复杂的部分了。

我们只在普通的二叉搜索树讲解删除操作，至于后面的AVLTree和红黑树的删除，原理是一样的，只是太复杂了，就不写了。

我们下面来看代码：（在下面的代码中，我们将会给出思路，即解释每行代码或者某段代码是什么意思）

千言万语，都在代码中间了。

#include<iostream>
#include<string>
using namespace std;
namespace K
{
  template<class K>
  struct BSTreeNode
  {
  BSTreeNode<K>* _left;        //存储左孩子的结点的指针
  BSTreeNode<K>* _right;       //存储右孩子的结点的指针
  K _key;                      //数值（数据域）
  BSTreeNode(const K& key)     //该结点的构造函数，我们初始化的时
    :_left(nullptr)          //候将所有的指针都赋值成空，然后key给到_key
    , _right(nullptr)
    , _key(key)
  {}
  };               //创建树节点，每一个树节点中，存储着左孩子和右孩子的指针
  template <class K>
  class BSTree                     //接下来是正式的二叉搜索树的类
  {
  typedef BSTreeNode<K> Node;  //先进行typedef一下
  public:
  BSTree()
    :_root(nullptr)         //构造函数
  {}
  ~BSTree()
  {
    _Destroy(_root);    //析构函数，调用_Destroy函数，前面带有_
  }                       //表示其是内置类型，我们将会把其定义为私有
  BSTree(const BSTree<K>& t)
  {
    _root = _Copy(t._root);  //拷贝构造，我们调用_Copy函数
  }
  BSTree<K>& operator=(BSTree<K> t) //操作符重载，赋值拷贝
  {
    swap(_root, t._root);    //通过交换结点指针的内容实现
    return *this;            //返回*this，即拷贝的对象的值
  }
  bool Insert(const K& key)    //插入（重点）
  {
    if (_root == nullptr)   //如果根为空
    {
    _root = new Node(key); //那就直接new一个新结点
    return true;           //然后结束
    }
    Node* parent = nullptr;   //先定义一个parent结点，用于记录
    Node* cur = _root;        //存储一下根结点的数据
    while (cur)               //如果cur不为空
    {
    if (cur->_key < key)  //判断，插入的结点是比现在的结点大还是小
    {                     //即先需要查找插入的位置，如果插入的比现在的要大，
      parent = cur;     //先记录当前位置
      cur = cur->_right;//然后往右走
    }
    else if (cur->_key > key)//同理，如果插入的结点比现在结点小
    {                        //先记录，再往左走
      parent = cur;
      cur = cur->_left;
    }
    else                    //否则，就直接返回false
    {                       //说明这个值已经存在了（默认不能被重复插入）
      return false;
    }
    }
    //出来后，此时cur为空
    cur = new Node(key);           //找到那个位置后，然后插入进去
    if (parent->_key < key)        //判断，看是应该插在其左边还是插在其右边
    {
    parent->_right = cur;      //连接起来（注意，刚刚的cur为空，得到new的新地址后
                               //，并未和parent连接起来）
    }
    else
    {
    parent->_left = cur;
    }
    return true;
  }
  void Inorder()       //中序遍历，用于打印的，没啥好说的了
  {
    _InOrder(_root); //我们让其调用内部接口，因为这里
    cout << endl;    //函数实现要传_root，而用户不需要
  }
  Node* find(const K& key)    //查找结点，比较简单
  {
    Node* cur = _root;
    while (cur) 
    {
    if (cur->_key < key)//比它大，就往右
    {
      cur = cur->_right;
    }
    else if (cur->_key < key)//比它小，就往左
    {
      cur = cur->_left;
    }
    else
    {
      return cur;       //如果不是前两种，那就找到了，返回该结点
    }
    }
    return nullptr;    //如果找到了空结点还没有找到，那么说明没有该结点，返回空
  }
  bool Erase(const K& key)   //删除结点
  {
    Node* parent = nullptr;  //让parent置空，等会用于记录
    Node* cur = _root;       //存储_root的数据
    while (cur)
    {
    if (cur->_key > key)  //同样的道理，先去查找要删除的结点
    {
      parent = cur;
      cur = cur->_left;
    }
    else if (cur->_key < key)
    {
      parent = cur;
      cur = cur->_right;
    }                     
    else
    {
      //找到了，开始删
      //分成三种情况 —— 左为空，右为空和左右都不为空
      //左右都为空的情况属于左为空（或者右为空）的情况的一种，所以就没有单独拿出来
      if (cur->_left == nullptr)   //如果其左为空
      {
      if (cur == _root)    //如果是根结点
      {
        _root = cur->_right;  //那就直接将其右侧的结点作为根结点（因为左为空）（不论右是否为空）
      }
      else                     //如果其不是根结点
      {
        if (parent->_left == cur)//如果该结点是其父亲的左孩子
        {
        parent->_left = cur->_right;  //那就将父亲的左孩子变成该结点的右孩子（因为左为空）
        }
        else                    //如果是右孩子
        {
        parent->_right = cur->_right;  //同理
        }                       //注意这里必须要去查找一下，否则可能会出现一些意想不到的错误
        delete cur;
      }
      }
      else if (cur->_right == nullptr)  //如果右为空
      {
      if (parent->_left == cur)     //同理，看cur是其父亲的左孩子还是右孩子
      {
        parent->_left = cur->_left;//如果是左孩子，那就将父亲的左孩子变成cur的左孩子（因为右为空）
      }
      else
      {
        parent->_right = cur->_left;//同理
      }
      delete cur;
      }
      else   //如果左右都不为空
      {
      //方法一：非递归方法
      // 我们的思路是找到最大的左或者最小的右来去替换它（这里我们找的是最小的右）
      //Node* minparent = cur;           //先记录
      //Node* tp = cur->_right;          //记录右孩子
      //while (tp->_left)                //如果右孩子的左不为空
      //{                                //那就一直往下找，知道找到为nullptr
      //  minparent = tp;
      //  tp = tp->_left;
      //}
      //cur->_key = tp->_key;           //将此时找到的结点的值给cur
      //if (minparent->_left == tp)     //如果它是左孩子
      //{
      //  minparent->_left = tp->_right; //那就将其右子树给它父亲的左孩子
      //}
      //else//特殊情况        注意，这里我们虽然找的是最小的右，但是仍可能存在一种情况：即minparent->_right === tp
            //这种情况存在于 只有一个根结点、并且根结点只有一个右孩子，需要删除右孩子的时候，
            //即上面的while循环根本没有进去
      //{
      //  minparent->_right = tp->_right;
      //}
      //delete tp;
      //
      //还可以这样：
      //方法二：（回调法）
      Node* minRight = cur->_right;  //同样先记录，记录的是右孩子（因为要找最小的右）
      while (minRight->_left)        //循环开始，直到找到空（即直到找到最小的右）
      {
        minRight = minRight->_left;
      } //找到之后
      K min = minRight->_key;      //将其存储起来
      this->Erase(min);             //回调该函数，删除（因为此时存储min结点一定有左孩子为空）
      cur->_key = min;              //把刚刚记录的值给cur，即完成了互换
      }
      return true;
    }
    }
    return false;                //没找到就删不了，返回false
  }
  Node* findR(const K& key)     //查找
  {
    return _FindR(_root, key); //直接调用内部函数，实现一层封装
  }
  bool InsertR(const K& key)   //插入同理（后面带有R的表示用递归的方法完成）
  {
    return _InsertR(_root, key);
  }
  private:
  Node* _root;
  Node* _FindR(Node* root, const K& key)   //递归的方法查找（上面用的是迭代）
  {
    if (root == nullptr)//如果找到空还没有找到，就返回空，表明没有找到
    {
    return nullptr;
    }
    if (root->_key < key)   //如果查找的数比当前结点要大，
    {
    return _FindR(root->_right, key);//那就继续往右找
    }
    else if (root->_key > key)
    {
    return _FindR(root->_left, key); //反之，就继续往左找
    }
    else
    {
    return root;        //找到了的话，就返回该结点
    }
  }
  bool _InsertR(Node*& root, const K& key)//递归方法插入
  {
    if (root == NULL)           //本质还是先查找，找到之后去插入
    {
    root = new Node(key);
    return true;
    }
    if (root->_key < key)
    {
    return _InsertR(root->_right, key);
    }
    else if (root->_key > key)
    {
    return _InsertR(root->_left, key);
    }
    else
    {
    return false;
    }
  }
  void _Destroy(Node* root)        //递归式删除
  {
    if (root == nullptr)
    return;
    _Destroy(root->_left);
    _Destroy(root->_right);
    delete root;
  }
  Node* _Copy(Node* root)   
  {
    if (root == nullptr)//一定要记得写如果是空就返回，否则将会栈溢出
    {
    return nullptr;
    }
    Node* copyNode = new Node(root->_key); //先定义一个结点，作为根结点，而后为递归产生的结点
    copyNode->_left = _Copy(root->_left);  //然后一一拷贝，递归式拷贝（可以画一个图去感受）
    copyNode->_right = _Copy(root->_right);
    return copyNode;
  }
  void _InOrder(Node* root)
  {                                  //中序遍历，没啥好说的了
    if (root == nullptr)
    return;
    _InOrder(root->_left);
    cout << root->_key << " ";
    _InOrder(root->_right);
  }
  };
}

上面的属于Key模型，实际上，我们还有模型

是什么意思呢？

1. K模型：K模型即只有key作为关键码，结构中只需要存储Key即可，关键码即为需要搜索到的值。

比如：给一个单词word，判断该单词是否拼写正确，具体方式如下：

以单词集合中的每个单词作为key，构建一棵二叉搜索树

在二叉搜索树中检索该单词是否存在，存在则拼写正确，不存在则拼写错误。

2. KV模型：每一个关键码key，都有与之对应的值Value，即的键值对。该种方式在现实生活中非常常见：比如英汉词典就是英文与中文的对应关系，通过英文可以快速找到与其对应的中文，英文单词与其对应的中文就构成一种键值对；

再比如统计单词次数，统计成功后，给定单词就可快速找到其出现的次数，单词与其出现次数就是就构成一种键值对。

比如：实现一个简单的英汉词典dict，可以通过英文找到与其对应的中文。

这里说一下，我们都是用pair<>来进行输入的。至于pair是啥

可以认为其实一个类，然后有两个模板。

实际上，有了上面的K模型之后，我们稍微修改修改就可以变成我们想要的模型了。

至于要改什么地方，笔者在这里只能说：改的地方很少，至于具体改了哪些地方，请读者自行欣赏吧。(这个地方只需要和上面的代码对比一下就可以了)

namespace KV
{
  template<class K, class V>
  struct BSTreeNode                
  {
  BSTreeNode<K ,V>* _left;
  BSTreeNode<K,V>* _right;
  K _key;
  V _value;
  BSTreeNode(const K& key,const V& value)
    :_left(nullptr)
    , _right(nullptr)
    , _key(key)
    ,_value(value)
  {}
  };
  template <class K, class V>
  class BSTree
  {
  typedef BSTreeNode<K ,V> Node;
  public:
  BSTree()
    :_root(nullptr)
  {}
  //涉及深浅拷贝，需要实现拷贝构造
  void Destroy()
  {
    _Destroy(_root);
  }
  BSTree(const BSTree<K,V>& t)
  {
    _root = _Copy(t._root);
  }
  BSTree<K,V>& operator=(BSTree<K,V> t)
  {
    swap(_root, t._root);
    return *this;
  }
  //bool Insert(const K& key)
  //{
  //  if (_root == nullptr)
  //  {
  //  _root = new Node(key);
  //  return true;
  //  }
  //  Node* parent = nullptr;
  //  Node* cur = _root;
  //  while (cur)
  //  {
  //  if (cur->_key < key)
  //  {
  //    parent = cur;
  //    cur = cur->_right;
  //  }
  //  else if (cur->_key > key)
  //  {
  //    parent = cur;
  //    cur = cur->_left;
  //  }
  //  else
  //  {
  //    return false;
  //  }
  //  }
  //  cur = new Node(key);           //找到那个位置，然后插入进去
  //  if (parent->_key < key)
  //  {
  //  parent->_right = cur;
  //  }
  //  else
  //  {
  //  parent->_left = cur;
  //  }
  //  return true;
  //}
  void _InOrder(Node* root)
  {
    if (root == nullptr)
    return;
    _InOrder(root->_left);
    cout << root->_key << ":"<<root->_value;
    _InOrder(root->_right);
  }
  void Inorder()
  {
    _InOrder(_root);
    cout << endl;
  }
  /*Node* find(const K& key)
  {
    Node* cur = _root;
    while (cur)
    {
    if (cur->_key < key)
    {
      cur = cur->_right;
    }
    else if (cur->_key < key)
    {
      cur = cur->_left;
    }
    else
    {
      return cur;
    }
    }
    return nullptr;
  }*/
  bool EraseR(const K& key)
  {
    return _EraseR(_root, key);
  }
  Node* findR(const K& key)
  {
    return _FindR(_root, key);
  }
  bool InsertR(const K& key,const V& value)
  {
    return _InsertR(_root, key,value);
  }
  private:
  Node* _root;
  Node* _FindR(Node* root, const K& key)
  {
    if (root == nullptr)
    {
    return nullptr;
    }
    if (root->_key < key)
    {
    return _FindR(root->_right, key);
    }
    else if (root->_key > key)
    {
    return _FindR(root->_left, key);
    }
    else
    {
    return root;
    }
  }
  bool _InsertR(Node*& root, const K& key,const V& value)
  {
    if (root == NULL)
    {
    root = new Node(key,value);
    return true;
    }
    if (root->_key < key)
    {
    return _InsertR(root->_right, key, value);
    }
    else if (root->_key > key)
    {
    return _InsertR(root->_left, key, value);
    }
    else
    {
    return false;
    }
  }
  bool _EraseR(Node*& root, const K& key)
  {
    if (root == nullptr)
    {
    return false;
    }
    if (root->_key == key)
    {
    /*Node* pt = root->_right;
    while (pt->_left != NULL)
    {
      pt = pt->_left;
    }
    root->_key = pt->_key;
    delete pt;*/
    if (root->_left == nullptr && root->_right == nullptr)
    {
      delete root;
      root = nullptr;
      return true;
    }
    else if (root->_left == nullptr)
    {
      Node* del = root;
      root = root->_right;
      delete del;
      //root = root->_right;
      return true;
    }
    else if (root->_right == nullptr)
    {
      Node* del = root;
      root = root->_left;
      delete del;
      return true;
    }
    else
    {
      Node* minparent = root;
      Node* tp = root->_right;
      while (tp->_left)
      {
      minparent = tp;
      tp = tp->_left;
      }
      //swap(tp,cur)//不需要这么复杂
      //还要再进一步地将其连接上
      root->_key = tp->_key;
      if (minparent->_left == tp)
      {
      minparent->_left = tp->_right;
      }
      else//特殊情况
      {
      minparent->_right = tp->_right;
      }
      delete tp;
      //Node*& pt = root->_right;//不可以这样去删除，这里只能中规中矩的删除，因为我们的规则关系是不能够乱动的
      //while (pt->_left)
      //{
      //  pt = pt->_left;
      //}
      //K min = pt->_key;             //保存数据的智慧
      // V valuemin = pt->_value;
      //this->_EraseR(pt, min);
      //root->_key = min;
      //root->value = valuemin
      return true;
    }
    }
    else if (root->_key > key)
    {
    return _EraseR(root->_left, key);
    }
    else if (root->_key < key)
    {
    return _EraseR(root->_right, key);
    }
    else
    {
    return false;
    }
  }
  void _Destroy(Node* root)
  {
    if (root == nullptr)
    return;
    _Destroy(root->_left);
    _Destroy(root->_right);
    delete root;
  }
  Node* _Copy(Node* root)
  {
    if (root == nullptr)
    {
    return nullptr;
    }
    Node* copyNode = new Node(root->_key,root->_value);
    copyNode->_left = _Copy(root->_left);
    copyNode->_left = _Copy(root->_right);
    return copyNode;
  }
  };
}
 关于这样的KV模型，我们下面还会反复地提到。
注意：
<单词，中文含义>为键值对构造二叉搜索树，注意：二叉搜索树需要比较，键值对比较时只比较
Key
查询英文单词时，只需给出英文单词，就可快速找到与其对应的key
我们以上面的代码给出一个例子：
#include "BSTree.h"
void test1()
{
  K::BSTree<int> t;
  int a[] = { 5,3,4,1,7,8,2,6,0,9 };
  for (auto e : a)
  {
  t.InsertR(e);
  }
  t.Inorder();
  t.Erase(7);
  t.EraseR(5);
  t.Inorder();
}
void test2()
{
  KV::BSTree<string, string> dict;
  dict.InsertR("string", "字符串");
  string str;
  while (cin >> str)
  {
  KV::BSTreeNode<string, string>* ret = dict.findR(str);
  if (ret == nullptr)
  {
    cout << "拼写错误" << endl;
  }
  else
  {
    cout <<  "中文翻译:" << ret->_value << endl;
  }
  }
}
void test3()
{
  string arr[] = {"苹果","香蕉", "苹果", "香蕉", "苹果" ,"西瓜" ,"香蕉" };
  KV::BSTree<string, int> countTree;
  for (const auto& str : arr)
  {
  auto ret = countTree.findR(str);
  if (ret == nullptr)
  {
    countTree.InsertR(str, 1);
  }
  else
  {
    ret->_value++;
  }
  }
  countTree.Inorder();
}
int main()
{
  test3();
    return 0;
}

运行截图（如下）：

1-2-4 二叉搜索树的性能分析

插入和删除操作都必须先查找，查找效率代表了二叉搜索树中各个操作的性能。

对有n个结点的二叉搜索树，若每个元素查找的概率相等，则二叉搜索树平均查找长度是结点在二叉搜索树的深度的函数，即结点越深，则比较次数越多。

但对于同一个关键码集合，如果各关键码插入的次序不同，可能得到不同结构的二叉搜索树

最优情况下，二叉搜索树为完全二叉树，其平均比较次数为：logN

最差情况下，二叉搜索树退化为单支树，其平均比较次数为：N/2

那能否进行改进，不论按照什么次序插入关键码，都可以是二叉搜索树的性能最佳？

答案就是AVLTree.

我们接下来就说AVLTree

2、AVLTree

2-1 AVLTree的概念

二叉搜索树虽可以缩短查找的效率，但如果数据有序或接近有序二叉搜索树将退化为单支树，查找元素相当于在顺序表中搜索元素，效率低下。因此，两位俄罗斯的数学家G.M.Adelson-Velskii和E.M.Landis在1962年发明了一种解决上述问题的方法：当向二叉搜索树中插入新结点后，如果能保证每个结点的左右子树高度之差的绝对值不超过1(需要对树中的结点进行调整)，即可降低树的高度，从而减少平均搜索长度。

说人话：在二叉搜索树的基础上，每一棵树的结点都可以认为存在一个平衡因子，平衡因子=右子树的深度-左子树的深度。通过一系列骚操作，能够使得平衡因子始终保持在 -1~1 之间。

这里需要注意一点，定义并不是说一定要有这个“平衡因子”这个概念，你可以没有，但是你要保证左子树的深度和右子树的深度的差的绝对值在1之内（小于等于1）。

而我们为了方便，就设立了这么一个平衡因子，便于我们调控。

现在问题的关键就是骚操作到底是什么操作？

这里笔者也就不卖关子了，也懒得通过引例啥的去一步一步引入了，直接说结论：

当插入一个结点之后，如果父节点的平衡因子变成了0，那么停止往上计算，插入完毕；（理由很简单，因为这个时候代表着插入新增结点并没有改变树的深度）

如果父节点的平衡因子为1或者-1，那么需要继续往上去算，即需要再去算父节点的父节点的平衡因子。

当平衡因子的绝对值超过1时，我们有四种方法来去让它重新会到原有的平衡，使平衡因子的绝对值回到1之内。

四种方法分别为：

左单旋；

右单旋；

左右单旋；

右左单旋。

后面两个从字面意思就可以看出其会前面两种的组合。

我们来分别说说吧：

2-1-1 左单旋：

我们可以这样来去理解：当出现右右这样的情况，使平衡因子失衡时，原有的父亲节点（值为30的结点）将60结点的左孩子挤掉，自己呢跑去卖乖，当它的左孩子。那么结点60原有的左孩子被挤掉之后，其左孩子就成孤儿了，所以要被领养，而刚好结点30此时没有右孩子了，所以就去做结点30的右孩子。

当然，这里只是一种记忆方式，实际的原理要求是要遵循二叉搜索树来完成的。

具体过程见上图。

至于代码，我们马上就说。

再来看

2-1-2 右单旋：

这种情况相当于左左的情况——插入的结点在最左边，左边连成一条线。

右单旋和左单旋的原理是一样的。

首先，30的右孩子（b）拿出来，让60去做30的右孩子，再让30原来的右孩子（b）去做60的左孩子。

2-1-3 左右单旋：

先左单旋，再右单旋。

运用场景：其是一条折线。即90（平衡因子超出的位置）、30、60和要新增的结点，其是一条折线。

因为你会发现，你单单只进行一次左单旋，是无法做到将整棵树弄平衡的。

折线开口朝右，那么就是左右单旋——即先左单旋，使得30、60、90在同一条线上（只是感官上能够看出其是在同一条线上），然后再右单旋。（具体过程如上图）

右左单旋：

微信图片_20221210120410.png

关于其具体旋转过程，我们就不再赘述了，各位类比即可。

2-2 总结：

假如以pParent为根的子树不平衡，即pParent的平衡因子为2或者-2，分以下情况考虑

1. pParent的平衡因子为2，说明pParent的右子树高，设pParent的右子树的根为pSubR

当pSubR的平衡因子为1时，执行左单旋

当pSubR的平衡因子为-1时，执行右左双旋

2. pParent的平衡因子为-2，说明pParent的左子树高，设pParent的左子树的根为pSubL

当pSubL的平衡因子为-1是，执行右单旋

当pSubL的平衡因子为1时，执行左右双旋

旋转完成后，原pParent为根的子树个高度降低，已经平衡，不需要再向上更新。

即父子的平衡因子是一正一负，那么就是双旋；如果是同号，那就是单旋。

接下来我们来看代码：（该有的代码注释已经全部标注出来了，一切尽在代码中）

#include<iostream>
#include<assert.h>
#include<string>
using namespace std;
template<class K, class V>
struct AVLTreeNode
{
  AVLTreeNode<K, V>* _left;
  AVLTreeNode<K, V>* _right;
  AVLTreeNode<K, V>* _parent;  //弄成一个三叉链
  int _bf;//暂且将其当作平衡因子
  pair<K, V> _kv;//好处是我如果返回值或者迭代器的时候，我可以直接就返回两个
  //解释一下这里的pair，实际上其就是一个类，它有两个值，一个用来存储key,一个用来存储value
  AVLTreeNode(const pair<K, V>& kv)        //结点的构造函数
  :_left(nullptr)
  , _right(nullptr)
  , _parent(nullptr)
  , _bf(0)
  ,_kv(kv)
  {}
};
template<class K, class V>
class AVLTree
{
public:
  typedef AVLTreeNode<K, V> Node;   
  AVLTree()           //树的构造函数
  :_root(nullptr)
  {}
  void _Destroy(Node* root)   //销毁函数（类比二叉搜索树）
  {
  if (root == nullptr)
  return;
  _Destroy(root->_left);
  _Destroy(root->_right);
  delete root;
  }
  ~AVLTree()//（类比二叉搜索树）
  {
  _Destroy(_root);
  _root = nullptr;
  }
  //拷贝构造和复制需要深拷贝
  pair<Node*,bool> Insert(const pair<K, V>& kv)       //我们重点来看插入
  {
  if (_root == nullptr)                           //前面该怎么做和搜索二叉树是一样的
  {
    _root = new Node(kv);                      
    return make_pair(_root,true);
  }
  Node* parent = _root, * cur = _root;
  while (cur)
  {
    if (cur->_kv.first > kv.first)
    {
    parent = cur;
    cur = cur->_left;
    }
    else if (cur->_kv.first < kv.first)
    {
    parent = cur;
    cur = cur->_right;
    }
    else
    {
    return make_pair(cur,false);
    }
  }
  cur = new Node(kv);
  Node* newnode = cur;
  if (parent->_kv.first < kv.first)
  {
    parent->_right = cur;
    cur->_parent = parent;
  }
  else
  {
    parent->_left = cur;
    cur->_parent = parent;
  }
  //从现在开始，需要去控制平衡。这也是AVLTree和普通二叉搜索树有区别的开始
  //控制平衡
  //1、控制平衡因子
  while (cur != _root)          //如果插入的cur不是根结点
  {
    if (parent->_right == cur)  //如果cur是右孩子
    {
    parent->_bf++;          //父亲的平衡因子++
    }
    else
    {
    parent->_bf--;           //否则就--
    }
    if (parent->_bf == 0)       //如果此时父亲结点的平衡因子为0，说明新结点的增加并未改变子树的高度
    {
    break;                  //那么就停止调节，直接跳出循环
    }
    else if (parent->_bf == 1 || parent->_bf == -1)
    {
    //parent所在子树的高度变了，会影响parent的parent
    //继续往上更新
    cur = cur->_parent;       //把cur->_parent给cur
    parent = parent->_parent; //parent的_parent给cur
    }
    else if(parent ->_bf == 2||parent->_bf ==-2)//倘若为2或者-2
    {
    //需要进行平衡调节
    if (parent->_bf == -2)     
    {
      if (cur->_bf == -1)  //如果是-2和-1，为左左，
      {
      //那就进行右单旋
      RotateR(parent);
      }
      else //  cur->_bf == 1，左右异号，折现开口向右
      {
      //那就进行左右双旋
      RotateLR(parent);
      }
    }
    else  //parent->_bf == 2
    {
      if (cur->_bf == 1)//为右右
      {
      RotateL(parent);//左单旋
      }
      else//cur->_bf == -1  异号且折线开口向左
      {
      RotateRL(parent);//进行右左双旋
      }
    }
    break;  //旋转后直接跳出
    }
    else  //如果都不是上面的情况，说明调节的有问题，直接结束进程
    {
    assert(false);
    exit(-1);
    }
  }
  return make_pair(newnode,true);  //插入成功，返回新结点和true
  }
  V& operator[](const K& key)  //对[]进行重载
  {
  pair<Node*, bool> ret = Insert(make_pair(key, V()));//直接调用Insert函数
  return ret.first->_kv.second;                //返回其Node结点的value
  }
  void RotateLR(Node* parent)    //左右双旋
  {
  Node* subL = parent->_left; 
  Node* subLR = subL->_right;//先将左右结点进行记录
  int bf = subLR->_bf;       //记录平衡因子
  RotateL(parent->_left);//先调用左单旋（以parent的左结点为函数的parent）
  RotateR(parent);       //再调用右单旋
  if (bf == -1)          //接下来分情况讨论，去调节平衡因子
  {
    subL->_bf = 0;
    parent->_bf = 1;
    subLR->_bf = 0;
  }
  else if (bf == 1)
  {
    subL->_bf = 0;
    parent->_bf = -1;
    subLR->_bf = 0;
  }
  else if (bf == 0)
  {
    subL->_bf = 0;
    parent->_bf = 0;
    subLR->_bf = 0;
  }
  else
  {
    assert(false);
  }
  //再去调节平衡因子
  }
  void RotateRL(Node* parent)
  {
  Node* subR = parent->_right;
  Node* subRL = subR->_left;
  int bf = subRL->_bf;
  RotateR(parent->_right);
  RotateL(parent);
  //平衡因子更新
  if (bf == 1)
  {
    subR->_bf = 0;
    parent->_bf = -1;
    subRL->_bf = 0;
  }
  else if (bf == -1)
  {
    parent->_bf = 0;
    subR->_bf = 1;
    subRL->_bf = 0;
  }
  else if (bf == 0)
  {
    parent->_bf = 0;
    subR->_bf = 0;
    subRL->_bf = 0;
  }
  else
  {
    assert(false);
  }
  }
  void RotateL(Node* parent)    //左单旋
  {
  Node* subR = parent->_right;   
  Node* subRL = subR->_left;
  Node* parentparent = parent->_parent;  //先记录
  parent->_right = subRL;
  if (subRL)
  {
    subRL->_parent = parent;
  }   //两个一组
  subR->_left = parent;
  parent->_parent = subR;//两个一组
  //连接主体，找到组织
  if (parent == _root)
  {
    _root = subR;
    subR->_parent = nullptr;
  }
  else
  {
    if (parentparent->_left == parent)
    {
    parentparent->_left = subR;
    }
    else
    {
    parentparent->_right = subR;
    }
    subR->_parent = parentparent;
  }
  subR->_bf = parent->_bf = 0;
  }
  void RotateR(Node* parent) //右单旋
  {
  Node* subL = parent->_left;
  Node* subLR = subL->_right;
  parent->_left = subLR;
  if (subLR)
  {
    subLR->_parent = parent;
  }
  subL->_right = parent;
  Node* parentparent = parent->_parent;
  parent->_parent = subL;
  if (parent == _root)
  {
    _root = subL;
    _root->_parent = nullptr;
  }
  else
  {
    if (parentparent->_left == parent)
    {
    parentparent->_left = subL;
    }
    else
    {
    parentparent->_right = subL;
    }
    subL->_parent = parentparent;
  }
  subL->_bf = parent->_bf = 0;
  }
  Node* Find(const K& key)
  {
  Node* cur = _root;
  while (cur)
  {
    if (cur->_kv.first < key)
    {
    cur = cur->_right;
    }
    else if (cur->_kv.first > key)
    {
    cur = cur->_right;
    }
    else
    {
    return cur;
    }
  }
  return nullptr;
  }
  bool Erase(const K& key)
  {
  //自己有兴趣实现
  return false;
  }
  void InOrder()
  {
  _InOrder(_root);
  }
  bool IsAVLTree()
  {
  return _IsBalance(_root);
  }
private:
  Node* _root;
  void _InOrder(Node* root)
  {
  if (root == nullptr)
  {
    return;
  }
  _InOrder(root->_left);
  cout << root->_kv.first << ":" << root->_kv.second << endl;
  _InOrder(root->_right);
  }
  bool _IsBalance(Node* root)
  {
  if (root == nullptr)
  {
    return true;
  }
  int leftHeight = _Height(root->_left);
  int rightHeight = _Height(root->_right);
  if (rightHeight - leftHeight != root->_bf)
  {
    cout << "平衡因子异常" << root->_kv.first << endl;
    return false;
  }
  return abs(rightHeight - leftHeight) < 2
    && _IsBalance(root->_left)
    && _IsBalance(root->_right);
  }
  int _Height(Node* root)
  {
  if (root == nullptr)
  {
    return 0;
  }
  int leftHeight = _Height(root->_left);
  int rightHeight = _Height(root->_right);
  return rightHeight > leftHeight ? rightHeight + 1 : leftHeight + 1;
  }
};

这就是AVLTree。

那红黑树呢？

我们继续来说。

3、红黑树

3-1 红黑树的概念：

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

对于红黑树而言，其可以理解为是近似平衡；而我们刚刚说的AVLTree，是严格平衡。

3-2 红黑树的性质：

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

2. 根节点是黑色的

3. 如果一个节点是红色的，则它的两个孩子结点是黑色的（不能有两个连续的红色结点）

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

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

比如，下面的这一颗树就是红黑树：

那红黑树是怎样实现插入并且能够调节平衡的呢？

1、首先，如果插入的结点是根结点，那么就标记为黑；

2、接下来的每个新增的结点，都默认是红色结点（因为其对原有的红黑树的破坏性与默认是黑色结点相比较小）。

3、如果存在了相邻的两个红色结点，那么此时就破坏了规则3。需要进行调整。

那怎么调整呢？

3-3 红黑树的调整

此时，我们已经确定的关系是这样的：

p1是黑的，p2和p4都是红的。p3暂时不知道是黑是红（甚至有可能不存在）

于是，我们要分情况讨论。

我们暂且把p3称为p2的兄弟，即p4的叔叔。

3-3-1 第一种情况：叔叔为红。

就是这样：

此时变动的规则是：

将父亲和叔叔都变成黑，然后将祖父变成红。

即变动以后为：

理由很简单：在上面所展示的树中，可能仅仅只是树的一个分支。而要保证规则4，就必须要改变后每一条路径上的黑色结点的数量不变。

如果不把祖父（即p1）的颜色修改为红，那么该分支上的两条路径，黑色结点就会多了一个

需要注意的是，如果p1是根结点，我们最终还应当将其变回黑色，否则就违背了规则2.

3-3-2 第二种情况：叔叔为黑色或者叔叔不存在

如果是这样一种情况，那么需要进行一次旋转。

如果是按照上图所示的情况，那么需要以p1为parent进行一次右单旋，然后将p2变成黑，将p1变成红。具体过程如下图所示：

微信图片_20221210120738.png

如果是在左边（对称镜像的位置也是一样的，需要进行一次左单旋）

3-3-3 针对叔叔为红或者叔叔不存的情况，还有一种可能，即新增结点位于p2的右孩子处。（情况三）

那么此时，需要进行双旋。

我们再来举一个例子：

如上图所示，假设存在这样一种情况，下面的结点在新增的时候，通过某种变换方式，让cur变成了红色。此时，先以p为根，进行一次左单旋；然后就变成了我们上面所说的情况了（即情况二所说），再进行一次右单旋即可。

好，我们接下来就来模拟实现红黑树。

还是那句话，一切尽在代码中，改注释的地方已经注释到位了。

#include<iostream>
using namespace std;
enum Colour
{
  RED,
  BLACK,
};
template<class K, class V>
struct RBTreeNode
{
  RBTreeNode<K, V>* _left;
  RBTreeNode<K, V>* _right;
  RBTreeNode<K, V>* _parent;
  pair<K, V> _kv;
  Colour _col;              //给出个参考颜色（用于标识红或者黑）
  RBTreeNode(const pair<K,V>& kv)  //红黑树结点的构造函数
  :_left(nullptr)
  ,_right(nullptr)
  ,_parent(nullptr)
  ,_kv(lv)
  ,_col(RED)
  {}
};
template<class K, class V>
class RBTree
{
  typedef RBTreeNode<K, V> Node;
public:
  RBTree()
  :_root(nullptr)      //构造函数初始化
  {}
  //拷贝构造和operator自己实现
  void Destroy(Node* root)//销毁函数
  {
  if (root == nullptr)
    return;
  Destroy(root->_left);  //通过不断递归来去实现，类比二叉搜索树
  Destroy(root->_right);
  delete root;
  }
  ~RBTree()            //析构函数——去调用销毁函数
  {
  Destroy(_root);
  }
  Node* Find(const K& key)  //查找（类比搜索二叉树）
  {
  Node* cur = _root;
  while (cur)
  {
    if (cur->_kv.first > key)
    {
    cur = cur->_left;
    }
    else if (cur->_kv.first < key)
    {
    cur = cur->_right;
    }
    else
    {
    return cur;
    }
  }
  return nullptr;
  }
  pair<Node* ,bool> insert(const pair<K, V>& kv)//插入
  {
  if (_root == nullptr)           
  {
    _root = new Node(kv);
    _root->_col = BLACK;
    return make_pair(_root, true);
  }
  Node* parent = nullptr;
  Node* cur = _root;
  while (cur)
  {
    if (cur->_kv.first <= kv.first)
    {
    parent = cur;
    cur = cur->_right;
    }
    else if(cur->_kv.first >kv.first)
    {
    parent = cur;
    cur-> = cur->_left;
    }
    else
    {
    return make_pair(cur, false);
    }
  }
  Node* newnode = new Node(kv);
  newnode->_col = RED;               //标记为红
  if (parent->_kv.first < kv.first)
  {
    parent->_right = newnode;
    newnode->_parent = parent;
  }
  else
  {
    parent->_left = newnode;
    newnode->_parent = parent;
  }
  cur = newnode;                         //前面的和搜索二叉树的插入完全一样，就标记了一下颜色。这里不再过多赘述
  while (parent && parent->_col == RED)  //如果父亲存在，且颜色为红色就要处理
  {
    //关键看叔叔
    Node* grandfather = parent->_parent;//并且祖父一定存在
    if (parent == grandfather ->  _left)   //如果父亲是祖父的左孩子
    {
    Node* uncle = grandfather->_right;    //那么叔叔就是祖父的右孩子
    if (uncle && uncle->_col == RED)      //如果叔叔存在且为红（情况一）
    {
      parent->_col = uncle->_col = BLACK;//把父亲和叔叔变成黑
      grandfather->_col = RED;    //祖父变成红
      //继续往上处理
      cur = grandfather;         //将祖父的位置给孙子
      parent = cur->_parent;     //父亲变为祖父的父亲
    }
    else  //情况2+3：叔叔不存在或者叔叔存在且为黑
    {
      //情况2：单旋
      if (cur == parent->_left)   //如果孩子是父亲的左孩子
      {
      RotateR(grandfather);  //右单旋
      grandfather->_col = RED;  //再变色
      parent->_col = BLACK;
      }
      else//情况3：双旋
      {
      RotateL(parent);
      RotateR(grandfather);
      cur->_col = BLACK;         //最终变的还是祖父的颜色和父亲的颜色
      grandfather->_col = RED;    //祖父的颜色变成红，父亲的颜色变成黑
      }
      break;
    }
    }
    else  //parent == grandparent -> _right   情况是相同的
    {
    Node* uncle = grandfather->_left;
    if (uncle && uncle->_col == RED)//情况1
    {
      uncle->_col == BLACK;
      grandfather->_col = RED;
      cur = grandfather;
      parent = cur->_parent;
    }
    else//情况2+3
    {
      if (cur == parent->_right)
      {
      RotateL(grandfather);
      parent->_col = BLACK;
      grandfather->_col = RED;
      }
      else //cur为父亲的左
      {
      //双旋
      RotateR(parent);
      RotateL(grandfather);
      cur->_col = BLACK;
      grandfather->_col = RED;
      }
      //插入结束
      break;
    }
    }
  }
  _root->_col = BLACK;
  return make_pair(newnode, true);
  }
  //剩余的就不解释了，和搜索二叉树、AVLTree都是一样的道理
  //只不过这里的旋转就不需要再调节平衡因子了。
  void RotateLR(Node* parent)
  {
  Node* subL = parent->_left;
  Node* subLR = subL->_right;
  RotateL(parent->_left);
  RotateR(parent);
  }
  void RotateRL(Node* parent)
  {
  Node* subR = parent->_right;
  Node* subRL = subR->_left;
  RotateR(parent->_right);
  RotateL(parent);
  }
  void RotateL(Node* parent)    //左单旋
  {
  Node* subR = parent->_right;
  Node* subRL = subR->_left;
  Node* parentparent = parent->_parent;
  parent->_right = subRL;
  if (subRL)
  {
    subRL->_parent = parent;
  }   //两个一组
  subR->_left = parent;
  parent->_parent = subR;//两个一组
  //连接主体，找到组织
  if (parent == _root)
  {
    _root = subR;
    subR->_parent = nullptr;
  }
  else
  {
    if (parentparent->_left == parent)
    {
    parentparent->_left = subR;
    }
    else
    {
    parentparent->_right = subR;
    }
    subR->_parent = parentparent;
  }
  }
  void RotateR(Node* parent) //右单旋
  {
  Node* subL = parent->_left;
  Node* subLR = subL->_right;
  parent->_left = subLR;
  if (subLR)
  {
    subLR->_parent = parent;
  }
  subL->_right = parent;
  Node* parentparent = parent->_parent;
  parent->_parent = subL;
  if (parent == _root)
  {
    _root = subL;
    _root->_parent = nullptr;
  }
  else
  {
    if (parentparent->_left == parent)
    {
    parentparent->_left = subL;
    }
    else
    {
    parentparent->_right = subL;
    }
    subL->_parent = parentparent;
  }
  }
  bool _CheckBlance(Node* root, int blackNum, int count)
  {
  if (root == nullptr)
  {
    if (count != blackNum)
    {
    cout << "黑色节点数量不等" << endl;
    }
    return true;
  }
  if (root->_col == RED && root->_parent->_col == RED)
  {
    cout << "存在连续的红色结点" << endl;
    return false;
  }
  if (root->_col == BLACK)
  {
    count++;
  }
  return _CheckBlance(root->_left,blackNum ,count)
    && _CheckBlance(root->_right, blackNum, count);
  }
  bool CheckBlance()
  {
  if (_root == nullptr)
  {
    return true;
  }
  if (_root->_col == RED)
  {
    cout << "根结点是红色的"<<endl;
    return false;
  }
  //找最左路径做黑色结点的参考值
  int blackNum = 0;
  Node* left = _root;
  while (left)
  {
    if (left->_col == BLACK)
    {
    blackNum++;
    }
    left = left->_left;
  }
  int count = 0;
  return _CheckBlance(_root,blackNum,count)
  }
private:
  Node* _root;
  }

说明：关于红黑树的删除，我们在这里就不做过多的探讨了，其实原理还是那个原理，结合着二叉搜索树的删除以及平衡调节的原理是可以弄出来的，但是由于其基本不会考，而我们并不是为了造轮子而造轮子，所以，有兴趣的同学可以自行下去尝试。

3-4 红黑树与AVL树的比较

红黑树和AVL树都是高效的平衡二叉树，增删改查的时间复杂度都是O( logN )，红黑树不追求绝对平衡，其只需保证最长路径不超过最短路径的2倍，相对而言，降低了插入和旋转的次数，所以在经常进行增删的结构中性能比AVL树更优，而且红黑树实现比较简单，所以实际运用中红黑树更多。

3-5 红黑树的应用

1. C++ STL库 -- map/set、mutil_map/mutil_set

2. Java 库

3. linux内核

4. 其他一些库

C++ 第八节&数据结构第七节 ——二叉搜索树 AVL树红黑树（底层原理图+模拟实现）

1、二叉搜索树

1-1、概念

1-2 二叉搜索树的增、删、查

1-2-1 二叉搜索树的增加（结点数据）

1-2-2二叉搜索树的查找

1-2-3 二叉搜索树的删除

1-2-4 二叉搜索树的性能分析

2、AVLTree

2-1 AVLTree的概念

2-1-1 左单旋：

2-1-2 右单旋：

2-1-3 左右单旋：

2-2 总结：

3、红黑树

3-1 红黑树的概念：

3-2 红黑树的性质：

3-3 红黑树的调整

3-3-1 第一种情况：叔叔为红。

3-3-2 第二种情况：叔叔为黑色或者叔叔不存在

3-3-3 针对叔叔为红或者叔叔不存的情况，还有一种可能，即新增结点位于p2的右孩子处。（情况三）

3-4 红黑树与AVL树的比较

3-5 红黑树的应用

热门文章

最新文章

相关课程

相关电子书

C++ 第八节&数据结构 第七节 ——二叉搜索树 AVL树 红黑树（底层原理图+模拟实现）

1、二叉搜索树

1-1、概念

1-2 二叉搜索树的增、删、查

1-2-1 二叉搜索树的增加（结点数据）

1-2-2二叉搜索树的查找

1-2-3 二叉搜索树的删除

1-2-4 二叉搜索树的性能分析

2、AVLTree

2-1 AVLTree的概念

2-1-1 左单旋：

2-1-2 右单旋：

2-1-3 左右单旋：

2-2 总结：

3、红黑树

3-1 红黑树的概念：

3-2 红黑树的性质：

3-3 红黑树的调整

3-3-1 第一种情况：叔叔为红。

3-3-2 第二种情况：叔叔为黑色或者叔叔不存在

3-3-3 针对叔叔为红或者叔叔不存的情况，还有一种可能，即新增结点位于p2的右孩子处。（情况三）

3-4 红黑树与AVL树的比较

3-5 红黑树的应用

热门文章

最新文章

相关课程

相关电子书

C++ 第八节&数据结构第七节 ——二叉搜索树 AVL树红黑树（底层原理图+模拟实现）