C++——AVL平衡二叉树
AVL是⼀颗空树，或者具备下列性质的⼆叉搜索树：它的 左右⼦树都是AVL树，且左右⼦树的⾼度差的绝对值不超过1。AVL树是⼀颗⾼度平衡搜索⼆叉树， 通过控制⾼度差去控制平衡。
引⼊⼀个平衡因⼦(balance factor)的概念，每个结点都有⼀个平衡因⼦， 任何结点的平衡因⼦等于右⼦树的⾼度减去左⼦树的⾼度 ，也就是说任何结点的平衡因⼦等于0/1/-1， AVL树并不是必须要平衡因⼦，但是有了平衡因⼦可以更⽅便我们去进⾏观察和控制树是否平衡。⾼度可以控制在logN ，那么增删查改的效率也可以控制在O ( logN ) ，相⽐⼆叉搜索树有了本质的提升
目录
一、AVL的结构
二、AVL的插入
1、搜索合适插入位置
2、新建一个节点，进行接入
3、平衡因子处理
4、插入节点源码
三、插入节点时旋转操作
1、右旋操作
处理subL结点
处理parent节点：
处理subLR结点：
平衡因子归零
右旋源码：
2、左旋操作
3、左右双旋
4、右左双旋
四、其他操作
1、查找
2、树高
3、平衡检测
4、层序打印AVL
一、AVL的结构
平衡二叉树结点结构
template <class K, class V>
class AVLNode
{
public:
AVLNode* _left;
AVLNode* _right;
AVLNode* _parent; 使用三叉链表来进行存储
pair<K, V> _key;
int _bf; bf为平衡因子
AVLNode(const pair<K, V>& key)
: _key(key)
, _left(nullptr)
, _right(nullptr)
, _parent(nullptr)
, _bf(0)
{}
};
平衡二叉树结构
template<class K, class V>
class AVLTree
{
typedef AVLTreeNode<K, V> Node;
public:
//...
private:
Node* _root = nullptr;
};二、AVL的插入
首先，根据之前二叉搜索树规则寻找一个合适的插入位置（小往左走，大往右走）
1、搜索合适插入位置
if (_root == nullptr)
{
_root = new Node(key);
return true;
}
Node* cur = _root;
Node* parent = nullptr;
// 1、利用cur 与 parent 不断向下进行迭代，寻找合适的插入位置
while (cur)
{
if (cur->_key.first > key.first)
{
parent = cur;
cur = cur->_left;
}
else if (cur->_key.first < key.first)
{
parent = cur;
cur = cur->_right;
}
else
{
cout << "该结点已经存在，插入失败" << endl;
return false;
}
}从而，找到合适的位置，新建一个节点，进行接入，接入的时候要判断父子直接的左右位置关系
（要注意每个节点都是一个三叉链表，对于新插入节点，左右孩子都是空不用处理，但需要帮它找到它的父亲，同时也要将它与它父亲进行双向链接）
2、新建一个节点，进行接入
// 2、此时 cur 来到了一个空位置，也就是要在此处进行插入，parent为其父节点 但要判断插入节点与parent的左右关系
cur = new Node(key);
if (cur->_key.first > parent->_key.first)
parent->_right = cur;
else
parent->_left = cur;
cur->_parent = parent;接下来就需要处理节点的平衡因子，新插入结点到根所在路径上的每个结点都需要更新平衡因子。
在一个while循环里面，while里面用parent判空，这里的cur从新插入结点开始，parent从新插入节点的父亲开始，俩者一起在新插入结点至根节点的这条路径进行不断向上更新平衡因子，并通过平衡因子之间的关系进行旋转。
具体的平衡因子更新：若cur是parent的左孩子 那么parent的平衡因子进行-- 反之++
也就是每次迭代更新父节点的平衡因子（在左边减 在右边加）
之后进行判断，当前更新之后的节点平衡因子是否合理，合理的AVL树平衡因子只有0 1 -1 三种情况
如果父亲的平衡因子变为0，则再往上的节点均平衡了，就不需要继续向上遍历了
变为1 或者 -1 就需要继续向上迭代并重复while操作。
如出现2 或者 -2 就需要进行旋转处理了。
3、平衡因子处理
// 3、由插入位置向上进行平衡因子的更新
while (parent)
{
if (cur == parent->_left) // 对插入节点的父亲的平衡因子进行更新
parent->_bf--;
else
parent->_bf++;
if (parent->_bf == 0)
break;// 更新结束
else if (parent->_bf == 1 || parent->_bf == -1)
{
cur = parent;
parent = parent->_parent;
}
else if (parent->_bf == 2 || parent->_bf == -2)
{
// 旋转操作
……………………………………
break;
}
else
{
assert(false);
}
}4、插入节点源码
bool Insert(const pair<K, V>& key)
{
if (_root == nullptr)
{
_root = new Node(key);
return true;
}
Node* cur = _root;
Node* parent = nullptr;
// 1、利用cur 与 parent 不断向下进行迭代，寻找合适的插入位置
while (cur)
{
if (cur->_key.first > key.first)
{
parent = cur;
cur = cur->_left;
}
else if (cur->_key.first < key.first)
{
parent = cur;
cur = cur->_right;
}
else
{
cout << "该结点已经存在，插入失败" << endl;
return false;
}
}
// 2、此时 cur 来到了一个空位置，也就是要在此处进行插入，parent为其父节点 但要判断插入节点与parent的左右关系
cur = new Node(key);
if (cur->_key.first > parent->_key.first)
parent->_right = cur;
else
parent->_left = cur;
cur->_parent = parent;
// 3、由插入位置向上进行平衡因子的更新
while (parent)
{
if (cur == parent->_left) // 对插入节点的父亲的平衡因子进行更新
parent->_bf--;
else
parent->_bf++;
if (parent->_bf == 0)
break;// 更新结束
else if (parent->_bf == 1 || parent->_bf == -1)
{
cur = parent;
parent = parent->_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);
}
}
return true;
}三、插入节点时旋转操作
1、右旋操作
如图 6 是新插入节点，可以插入7的左也可以插入7的右（浅蓝色结点）
其中进行右旋操作后，红色部分也就是subL的左指针与parent的右指针是不需要变动的
分别处理subL parent subLR即可，即右旋操作也就是更新处理这三个结点的指针指向问题（同时需要注意每个节点都是三叉链表，需要检查他们各自的左、右、父指针 以及平衡因子归零）
处理subL结点
需要注意subL可能会成为根节点，将subL的父指针指空，并将根结点_root进行更新
若不是根节点，那么就需要使用ppNode来保存parent的父亲结点，并将subL与ppNode进行双向链接。
Node* subL = parent->_left;
Node* subLR = subL->_right;
// 更新subL的父指针，俩种情况
if (parent == _root)
{
subL->_parent = nullptr;
_root = subL;
}
else
{
Node* ppNode = parent->_parent; // 需要找parent的父亲结点
if (parent == ppNode->_left) // 并且判断parent与其父亲的左右关系
ppNode->_left = subL;
else
ppNode->_right = subL;
subL->_parent = ppNode;
}
// 更新subL的右
subL->_right = parent;处理parent节点：
// 更新parent的父和左指针
parent->_parent = subL;
parent->_left = subLR;处理subLR结点：
// 再subLR存在的情况下 更新它的_parent
if (subLR)
{
subLR->_parent = parent;
}平衡因子归零
//更新平衡因子
parent->_bf = subL->_bf = 0;右旋源码：
void RotateR(Node* parent)
{
Node* subL = parent->_left;
Node* subLR = subL->_right;
// 更新subL的父指针，俩种情况
if (parent == _root)
{
subL->_parent = nullptr;
_root = subL;
}
else
{
Node* ppNode = parent->_parent; // 需要找parent的父亲结点
if (parent == ppNode->_left) // 并且判断parent与其父亲的左右关系
ppNode->_left = subL;
else
ppNode->_right = subL;
subL->_parent = ppNode;
}
// 更新subL的右
subL->_right = parent;
// 更新parent的父和左指针
parent->_parent = subL;
parent->_left = subLR;
// 再subLR存在的情况下 更新它的_parent
if (subLR)
{
subLR->_parent = parent;
}
//更新平衡因子
parent->_bf = subL->_bf = 0;
}
2、左旋操作
注意parent是否为根的情况、将subRL接入parent的右孩子时，需要对subRL进行判空操作
void RotateL(Node* parent)
{
Node* subR = parent->_right;
Node* subRL = subR->_left;
// 更新了subR的_parent指针
if (parent == _root)
{
subR->_parent = nullptr;
_root = subR; // 只有parent为根的时候才更新subR为根
}
else
{
Node* ppNode = parent->_parent;
if (ppNode->_left == parent)
ppNode->_left = subR;
else
ppNode->_right = subR;
subR->_parent = ppNode;
}
// 更新subR的_left指针
subR->_left = parent;
// 更新parent的父和右
parent->_parent = subR;
parent->_right = subRL;
// 出错点2 ： bf应该为右减左
// 在此处更新_root 只有需要更改根的时候才需要进行更新_root
// _root = subR; 卡bug的一行错误代码
// 更新suRL
if (subRL)
{
subRL->_parent = parent;
}
// 更新平衡因子
subR->_bf = parent->_bf = 0;
}3、左右双旋
9结点下有俩个位置可以进行插入，上图 ⑧ 和 O 分别为俩种位置的旋转情况
void RotateLR(Node* parent)
{
Node* subL = parent->_left;
Node* subLR = subL->_right;
int bf = subLR->_bf; // 使用该平衡因子来判断最终的情况是哪一种
RotateL(subL);
RotateR(parent);
// 通过bf来确定旋转后的结构 进而更新各个节点的平衡因子
if (bf == 0)
{
subLR->_bf = 0;
subL->_bf = 0;
parent->_bf = 0;
}
else if (bf == -1)
{
subLR->_bf = 0;
subL->_bf = 0;
parent->_bf = 1;
}
else if (bf == 1)
{
subLR->_bf = 0;
subL->_bf = -1;
parent->_bf = 0;
}
else
assert(false);
}4、右左双旋
void RotateRL(Node* parent)
{
Node* subR = parent->_right;
Node* subRL = subR->_left;
int bf = subRL->_bf; // 使用该平衡因子来判断最终的情况是哪一种
RotateR(subR);
RotateL(parent);
// 通过bf来确定旋转后的结构 进而更新各个节点的平衡因子
if (bf == 0)
{
subRL->_bf = 0;
subR->_bf = 0;
parent->_bf = 0;
}
else if (bf == -1)
{
subRL->_bf = 0;
subR->_bf = 1;
parent->_bf = 0;
}
else if (bf == 1)
{
subRL->_bf = 0;
subR->_bf = 0;
parent->_bf = -1;
}
else
assert(false);
}四、其他操作
1、查找
Node* Find(const K& key)
{
Node* cur = _root;
while (cur)
{
// 和二叉排序树类似，不过这里的结点是 const pair<K, V>& _key
// 所以比较的时候使用 cur->_key.first 来访问第一个关键字
if (cur->_key.first > key)
cur = cur->_left;
else if (cur->_key.first < key)
cur = cur->_right;
else
return cur;
}
return nullptr;
}2、树高
int Height()
{
return _Height(_root);
}
// 求树高度 返回根左右高度最大+1
int _Height(Node* root)
{
if (root == nullptr)
return 0;
int left_Height = _Height(root->_left);
int right_Height = _Height(root->_right);
return left_Height > right_Height ? left_Height + 1 : right_Height + 1;
}3、平衡检测
bool _Is_Balance_Tree(Node* root)
{
if (nullptr == root)
return true;
int left_Height = _Height(root->_left);
int right_Height = _Height(root->_right);
int bf = right_Height - left_Height;
出错点2 ： bf应该为右减左 导致309的assert一直断言出错
if (abs(bf) >= 2) // 求出左右子树高度 作差并判断平衡因子
return false;
if (root->_bf != bf)
309 assert(false);
// 如果左右子树均为平衡二叉树，那么该树即为一颗平衡二叉树
return _Is_Balance_Tree(root->_left) && _Is_Balance_Tree(root->_right);
}
bool Is_Balance_Tree()
{
if (_Is_Balance_Tree(_root))
return true;
else
return false;
}4、层序打印AVL
void Print()
{
CX_Print(_root);
}
void CX_Print(Node* parent)
{
queue<Node*> q;
vector<Node*> res;
q.push(parent);
while (!q.empty())
{
Node* cur = q.front();
res.push_back(cur);
q.pop();
if (cur->_left)
q.push(cur->_left);
if (cur->_right)
q.push(cur->_right);
}
for (Node* key : res)
{
cout << key->_key.first << " ";
}
cout << endl;
}