【C++】AVL树和红黑树（插入和测试详解）

了解AVL树是为了了解红黑树，了解红黑树是为了更好的理解set和map。

1、AVL树

AVL树是在二叉搜索树的基础上进行了严格的平衡，能做到平衡的关键是通过平衡因子以及旋转。
AVL树有以下特性：

1. 任何根的左右子树高度之差(简称平衡因子)的绝对值不超过1(-1/0/1)。
2. 其中平衡因子是用右子树高度减去左子树高度。
3. 任何子树都是AVL树。

下面实现的AVL树还是KV结构的。

AVL树节点定义

#include <iostream>
#include <assert.h>
using namespace std;template<class K, class V>
struct AVLTreeNode
{//三叉链结构方便访问父节点struct AVLTreeNode<K, V>* _left;struct AVLTreeNode<K, V>* _right;struct AVLTreeNode<K, V>* _parent;pair<K, V> _kv; //键值对 里面存储key和valueint _bf; //平衡因子AVLTreeNode(const pair<K, V>& kv):_left(nullptr),_right(nullptr),_parent(nullptr),_kv(kv),_bf(0)
};template<class K, class V>
class AVLTree
{typedef AVLTreeNode<K, V> Node;
public:private:Node* root = nullptr;
};

 

1.1 AVL树的插入

1、AVL树的插入首先一开始和二叉搜索树的插入一样，先确定插入的位置，再和父节点链接。
 
2、插入完后，可能会破坏AVL树结构，所以要判断平衡因子。
插入新结点后，平衡因子会出现三种情况。

 
3、当平衡因子出现了-2或2的情况，这个时候就需要对parent进行旋转。
旋转有以下情况。

bool insert(const pair<K, V>& kv){if (_root == nullptr){_root = new Node(kv);return true;}Node* cur = _root;Node* parent = _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 false;}}cur = new Node(kv);//只能用kv值来确定parent和cur的指向if (parent->_kv.first < kv.first){parent->_right = cur;cur->_parent = parent;}else{parent->_left = cur;cur->_parent = parent;}//判断平衡因子while (parent){if (parent->_left == cur){//根节点左边插入节点，根的平衡因子-1parent->_bf--;}else{//根节点右边插入节点，根的平衡因子+1parent->_bf++;}//说明之前是-1或1，变为平衡if (parent->_bf == 0){break;}else if (parent->_bf == 1 || parent->_bf == -1){//下面子树高度差也影响了上面的根结点，所以需要向上调整cur = parent;parent = cur->_parent;}else if (parent->_bf == 2 || parent->_bf == -2){//这个时候就需要旋转，使得树平衡if (parent->_bf == -2 && cur->_bf == -1){//这是右旋转的情况RotateR(parent);}else if (parent->_bf == 2 && cur->_bf == 1){RotateL(parent);}else if (parent->_bf == -2 && cur->_bf == 1){RotateLR(parent);}else if (parent->_bf == 2 && cur->_bf == -1){RotateRL(parent);}else{assert(false);}//旋转完后，结构平衡，退出break;}else{//如果平衡因子出现其它情况，说明错了assert(false);}}//whilereturn true;}

旋转：

	//右旋转void RotateR(Node* parent){//从下到上依次修改Node* sub = parent->_left;Node* subR = sub->_right;//先改变最下面的subR结点parent->_left = subR;if (subR){subR->_parent = parent;}//再改变parent结点sub->_right = parent;Node* ppnode = parent->_parent;parent->_parent = sub;//最后改变sub结点if (ppnode == nullptr){_root = sub;_root->_parent = nullptr;}else{if (ppnode->_left == parent){ppnode->_left = sub;}else{ppnode->_right = sub;}sub->_parent = ppnode;}parent->_bf = sub->_bf = 0;}//左旋和右旋类似void RotateL(Node* parent){Node* sub = parent->_right;Node* subL = sub->_left;parent->_right = subL;if (subL){subL->_parent = parent;}sub->_left = parent;Node* ppnode = parent->_parent;parent->_parent = sub;if (ppnode == nullptr){_root = sub;_root->_parent = nullptr;}else{if (ppnode->_left == parent){ppnode->_left = sub;}else{ppnode->_right = sub;}sub->_parent = ppnode;}parent->_bf = sub->_bf = 0;}void RotateLR(Node* parent){Node* subL = parent->_left;Node* subLR = subL->_right;//保存subLR的平衡因子，为了知道从subLR哪边插入int bf = subLR->_bf;RotateL(parent->_left);RotateR(parent);if (bf == -1) // subLR左子树新增{subL->_bf = 0;parent->_bf = 1;subLR->_bf = 0;}else if (bf == 1) // subLR右子树新增{parent->_bf = 0;subL->_bf = -1;subLR->_bf = 0;}else if (bf == 0) // subLR自己就是新增{parent->_bf = 0;subL->_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) // subRL左子树新增{subR->_bf = 1;parent->_bf = 0;subRL->_bf = 0;}else if (bf == 1) // subRL右子树新增{parent->_bf = -1;subR->_bf = 0;subRL->_bf = 0;}else if (bf == 0) // subRL自己就是新增{parent->_bf = 0;subR->_bf = 0;subRL->_bf = 0;}else{assert(false);}}

可能会有的问题解释（以下是自己的理解）：

1、如何想到旋转的情况？
其实从所有情况看就这两个情况以及他们的翻转，记住它们两个就好了。

 
2、如何看左右旋？
拿上图举例，左边是一个右旋能平衡的场景，只需要将最高的结点往右放就行。
右边是一个双选的场景，先将中间结点左旋，就成了图左边的场景，再右旋就行。

 

1.2 总结与测试AVL树

AVL树重点关注的是其平衡因子和选择如何使得AVL树平衡，通过插入了解就足够了。
下面是如何测试结果是AVL树：
1、通过每个结点的左右子树的高度判断平衡因子是否符合要求。
2、通过小和大的测试用例测试是不是AVL树

#pragma once
#include <iostream>
#include <assert.h>
using namespace std;template<class K, class V>
struct AVLTreeNode
{struct AVLTreeNode<K, V>* _left;struct AVLTreeNode<K, V>* _right;struct AVLTreeNode<K, V>* _parent;pair<K, V> _kv;int _bf;AVLTreeNode(const pair<K, V>& kv):_left(nullptr),_right(nullptr),_parent(nullptr),_kv(kv),_bf(0){}
};template<class K, class V>
class AVLTree
{typedef AVLTreeNode<K, V> Node;
public:bool insert(const pair<K, V>& kv){}void RotateR(Node* parent){}void RotateL(Node* parent){}void RotateLR(Node* parent){}void RotateRL(Node* parent){}int Height(Node* root){if (root == nullptr){return 0;}int leftHight = Height(root->_left);int rightHight = Height(root->_right);return leftHight > rightHight ? leftHight + 1 : rightHight + 1;}bool IsBalanceTree(){return  _IsBalanceTree(_root);}bool _IsBalanceTree(Node* parent){if (parent == nullptr){return true;}int leftHight = Height(parent->_left);int rightHight = Height(parent->_right);int diff = rightHight - leftHight;if (diff != parent->_bf || (diff > 1 || diff < -1)){cout << "有错" << endl;return false;}return _IsBalanceTree(parent->_left) && _IsBalanceTree(parent->_right);}void Inorder(){_Inorder(_root);}void _Inorder(Node* root){if (root == nullptr)return;_Inorder(root->_left);cout << root->_kv.first << ":" << root->_kv.second << endl;_Inorder(root->_right);}
private:Node* _root = nullptr;
};//出错用小用例调
void test1()
{int arr[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };int arr2[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 };AVLTree<int, int> t;for (auto& e : arr){if(e == 18){	//调试断点int a = 0;}t.insert(make_pair(e, e));t.IsBalanceTree();}t.Inorder();
}//没错用多数据看看能不能过
#include <cstdlib>
void test2()
{srand(time(NULL));AVLTree<int, int> t;for (int i = 0; i < 100000; ++i){int num = rand() % 10000;t.insert(make_pair(num, num));}t.IsBalanceTree();
}

 

2、红黑树

AVL树因为其严格的平衡导致它因为大量的旋转导致效率相较红黑树低。

红黑树不要求严格平衡，它为每个结点加上颜色区分，使得它趋向于平衡。它有着以下规定。

1. 根节点必须是黑色。
2. 根节点颜色要么是红色，要么是黑色。
3. 红色结点不能连续。（也就是如果一个结点是红的，其两个子结点都是黑的）
4. 每条路径下的黑色结点树要一样。
5. 叶子结点都是黑色结点（这里叶子结点代表NULL结点）

可能概念理解起来很抽象，我们通过代码一步步来。

首先搭建红黑树的框架。
大致和AVL树一样，只不过没有平衡因子，换成了颜色。

#include <iostream>
#include <assert.h>
using namespace std;enum Color { RED, BLACK };template<class K, class V>
struct RBTreeNode
{struct RBTreeNode<K, V>* _left;struct RBTreeNode<K, V>* _right;struct RBTreeNode<K, V>* _parent;pair<K, V> _kv;Color _col;RBTreeNode(const pair<K, V>& kv):_kv(kv), _left(nullptr), _right(nullptr), _parent(nullptr), _col(BLACK){}
};template<class K, class V>
class RBTree
{typedef RBTreeNode<K, V> Node;
public:
private:Node* _root = nullptr;
};

2.1 红黑树的插入

1、首先如果根是空，新建的结点一定是黑色结点。这很好理解。
2、那么如果是后面创建的结点，是黑色还是红色呢？
 2.1 如果是黑色结点，那么想象一下，给某个路径添加一个黑色结点，使得这个路径的黑结点数量和其他路径不同，直接导致整个树不满足红黑树条件，直接破坏整个红黑树。
 2.2 如果是红色结点，最差只会出现两个红色结点相连的情况，只影响这个子树。
 
 所以综上选择影响最少的，选择创建红色结点。
3、插入前面和搜索树一样，得先确认插入的位置，以及和父节点链接。
4、调整红黑树


除此以外当然还有翻转的另一类情况。

bool insert(const pair<K, V>& kv){if (_root == nullptr){_root = new Node(kv);_root->_col = BLACK;return true;}Node* cur = _root;Node* parent = _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 false;}}cur = new Node(kv);cur->_col = RED;if (parent->_kv.first < cur->_kv.first){parent->_right = cur;cur->_parent = parent;}else{parent->_left = cur;cur->_parent = parent;}//调整//parent为红，代表插入的子节点也为红，需要调整。while (parent && parent->_col == RED){Node* grandparent = parent->_parent;//首先是第一类父亲结点在祖父结点左边，叔叔结点在右边的一类情况。if (parent == grandparent->_left){Node* uncle = grandparent->_right;if (uncle && uncle->_col == RED){//第一种情况 叔叔结点存在且为红色parent->_col = BLACK;uncle->_col = BLACK;grandparent->_col = RED;//向上调整，根节点的情况可以跑完整个调整，再设置_root->_col = BLACK;cur = grandparent;parent = cur->_parent;}else{//这一类是叔叔结点不存在以及存在为黑色//因为处理方法都是一样的，所以只要再区分直线型和折线型。if (parent->_right == cur){//折线的情况RotateL(parent);RotateR(grandparent);cur->_col = BLACK;grandparent->_col = RED;}else{//直线的情况RotateR(grandparent);parent->_col = BLACK;grandparent->_col = RED;}break;}}else{//这一类是上面翻转，一样的处理，但注意方向Node* uncle = grandparent->_left;if (uncle && uncle->_col == RED){parent->_col = BLACK;uncle->_col = BLACK;grandparent->_col = RED;cur = grandparent;parent = cur->_parent;}else{if (parent->_right == cur){RotateL(grandparent);parent->_col = BLACK;grandparent->_col = RED;}else{RotateR(parent);RotateL(grandparent);cur->_col = BLACK;grandparent->_col = RED;}break;}}}//最后确保根节点为黑。_root->_col = BLACK;return true;}//剩下左右旋转的代码和AVL中的一样。

如果记忆红黑树的情况？（个人方式）
首先要记得红黑树的特性，根一定是黑结点，想清楚为什么插入要插红结点，这样能更情况红黑树的特性。
 
像情况一的推理一样，先插入黑色的根节点，再插入红结点，层序插入直到出现问题，此时面对第一个情况，叔叔结点存在并且为红色。
 
然后考虑叔叔结点为黑和不存在的情况，因为要旋转，再根据AVL树中记忆的两个情况，推出除了直线型情况，还有折线型情况。

2.2 红黑树的测试

在测试中，需要判断的

1. 根要为黑结点。
2.判断父子结点不能都为红
3.确保每条路径的黑结点数相同（这里通过先计算一条路径的黑结点数，再和每一条路径比对）

bool Check(Node* proot, int count, int ref){if (proot == nullptr){//检查黑结点if (count != ref){cout << "出现路径黑结点树不同" << endl;return false;}return true;}Node* parent = proot->_parent;if (parent && (parent->_col == RED && proot->_col == RED)){cout << "出现了连续的红结点" << endl;return false;}if (proot->_col == BLACK){count += 1;}return Check(proot->_left, count, ref) && Check(proot->_right, count, ref);}bool IsRBTree(){if (_root == nullptr){return true;}if (RED == _root->_col){cout << "根节点不能为红色" << endl;return false;}int ref = 0;Node* checkblack = _root;while (checkblack){if (BLACK == checkblack->_col){ref++;}checkblack = checkblack->_left;}return Check(_root, 0, ref);}

本节完~