(AVL)平衡二叉树

还是照旧，本篇主要讲一下代码实现，AVL相关的定义什么的这里不多赘述。

AVL树就是为了解决bst树出现了“线性”的问题，而发明的。什么是线性的就是一棵bst树全都只有左子树或者全都只有右子树，能想象来吧。

LL型调整(左旋)

RR型调整（右旋）

LR调整

RL调整

代码实现：

因此呢AVL树一定是一棵bst树。不了解bst的可以先看看我这篇文章：(BST) 二叉排序树

AVL树是一类特殊的二叉排序树，它或者为空树，或者其左右子树都是平衡二叉排序树，而且其左右的子数高度之差绝对值不超过1.为了保证相对平衡，每次插入元素都会做相应的旋转

上面说了为了让avl树能保持平衡，每次插入节点后不平衡了就需要调整，旋转。

这样的话就衍生出来了avl的四种旋转方式，四种旋转方式搞懂了，avl的创建就没问题了

下面说说四种调整方式

LL型调整(左旋)

A的左孩子的左孩子插入新的节点，导致A的平衡因子从1变为2，不在满足根本性质[-1,1]，所以需要通过旋转。显然，按照大小关系，结点B应作为新的根结点，其余两个节点分别作为左右孩子节点才能平衡，这样看来，仿佛A结点绕结点B顺时针旋转一样。

当在节点5的左子树中插入节点的时候而导致不平衡。这种情况调整如下：首先将元素5的左孩子2提升为新的根结点；然后将原来的根结点元素5变为元素2的右孩子；其他各子树按大小关系连接。

RR型调整（右旋）

在元素5的右孩子的右孩子插入新的节点，导致元素5的平衡因子从-1变为-2，不在满足根本性质[-1,1]，所以需要通过旋转。显然，按照大小关系，结点元素7应作为新的根结点，其余两个节点分别作为左右孩子节点才能平衡，这样看来，仿佛节点元素5绕结点元素7逆时针旋转一样。

LR调整

节点元素5的左孩子的右子树上插入新节点，导致不平衡。此时元素5的平衡因子由1变为2。第一张图是LR型的最简单形式。显然，按照大小关系，元素3应作为新的根结点，其余两个节点分别作为左右孩子节点才能平衡。

节点元素6增加一个左孩子，导致元素4变得不平衡。先顺时针旋转元素7再逆时针旋转4元素达到平衡。

RL调整

当在元素5的右孩子的左子树增加一个节点7的时候，会造成不平衡的情况。先逆时针旋转成RR情况，再将元素5顺时针旋转。

第二种情况方法类似，看起来会复杂一点。当在元素7得左孩子6增加左孩子元素5得时候，导致元素4变得不平衡。那么先顺时针调整元素7，再逆时针调整元素4

代码实现：

主类大概这样：

class AVLNode {
public:AVLNode():m_left(nullptr),m_right(nullptr),m_bf(0){}AVLNode(int v):m_value(v), m_left(nullptr), m_right(nullptr), m_bf(0) {}int m_value;AVLNode *m_left;AVLNode *m_right;int m_bf;//平衡因子，该结点左右子树高度(深度)差
};
class AVLTree {
public:AVLTree() :m_root(nullptr){}void InsertAVLTree(int v) {InsertAVLTree(m_root, v);}//传指针 再引用直接就在原来的树上修改了//斜线       void RotateRR(AVLNode*& t);//右旋void RotateLL(AVLNode*& t);//左旋//折线void RotateRL(AVLNode*& t);//右左旋void RotateLR(AVLNode*& t);//左右旋void InsertAVLTree(AVLNode* &t, int v);//插入void DelAVLTree(int key);//删除当前key这个值void TTer(AVLNode*& t);//中序遍历AVLNode* m_root;
};

四个调整函数：

void AVLTree::RotateLL(AVLNode*& t)
{AVLNode* child = t;t = child->m_right;child->m_right = t->m_left;t->m_left = child;t->m_bf = child->m_bf = 0;
}
void AVLTree::RotateRR(AVLNode*& t)
{AVLNode* child = t;t = child->m_left;child->m_left = t->m_right;t->m_right = child;t->m_bf = child->m_bf = 0;
}
void AVLTree::RotateRL(AVLNode*& t)
{AVLNode* childL = t;AVLNode* childR = t->m_right;t = childR->m_left;//先右旋//将t的右孩子作为childR的左孩子，childR作为t的右孩子childR->m_left = t->m_right;t->m_right = childR;if (t->m_bf >= 0) {childR->m_bf = 0;}else {childR->m_bf = 1;}//再左旋childL->m_right = t->m_left;//左子树t->m_left = childL;if (t->m_bf==1) {childL->m_bf = -1;}else {childL->m_bf = 0;}t->m_bf = 0;
}
void AVLTree::RotateLR(AVLNode*& t)
{AVLNode* childR = t;AVLNode* childL = t->m_left;t = childL->m_right;//先左旋childL->m_right = t->m_left;//左子树t->m_left = childL;if (t->m_bf <= 0){childL->m_bf = 0;}else{childL->m_bf = -1;}//再右旋childR->m_left = t->m_right;//右子树t->m_right = childR;if (t->m_bf ==-1){childR->m_bf = 1;}else{childR->m_bf = 0;}t->m_bf = 0;
}

AVL的插入创建

void AVLTree::InsertAVLTree(AVLNode*& t, int v)
{AVLNode* p = t;AVLNode* parent = nullptr;stack<AVLNode*>sk;//存储路径上的所有节点while (p != nullptr) {if (p->m_value == v) {return;}parent = p;sk.push(parent);//入栈为计算插入新节点后路径上父辈的bfif (v < p->m_value){p = p->m_left;}else{p = p->m_right;}}//用v生成新节点p = new AVLNode(v);if (parent == nullptr){t = p;return;}//将p链接到树中对应的位置if (v < parent->m_value) {parent->m_left = p;}else {parent->m_right = p;}//计算bfwhile (!sk.empty()){parent = sk.top();sk.pop();//这里我们用右边减左边来算if (parent->m_left == p)//如果此时p插到了parent的左边{parent->m_bf--;}else{parent->m_bf++;}if (parent->m_bf == 0)//一定平衡着,高度没有发生变化{/*  bf-1     30   2插入个4变成了0     30   2   4*/break;}if (abs(parent->m_bf) == 1){//如果插入后bf绝对值等于1//那么有可能不平衡，需要往上看p = parent;}else{//父结点的bf绝对值为2，此时作为最小不平衡子树，开始旋转int flag = parent->m_bf > 0 ? 1 : -1;if (p->m_bf == flag)//斜线,同号{if (flag == -1)//右旋	RotateRR(parent);else//左旋		RotateLL(parent);}else {//折线，不同号if (flag == 1)//右高，先右旋再左旋{RotateRL(parent);}else{//先左旋再右旋RotateLR(parent);}}	break;}}//旋转后需要进行调整，if (sk.empty())//此时栈空了说明不用链接了{t = parent;}else{AVLNode* q = sk.top();if (q->m_value > parent->m_value)//栈顶大于parent，往左链接{q->m_left = parent;}else{q->m_right = parent;}}
}

AVL删除特定值节点

void AVLTree::DelAVLTree(int k)//删除当前key这个值
{AVLNode* p = m_root;AVLNode* parent = NULL, * ppr = NULL;stack<AVLNode*> st;while (p){if (p->m_value == k)break;parent = p;st.push(parent);if (k < p->m_value)p = p->m_left;elsep = p->m_right;}if (p == NULL)return;AVLNode* q = NULL;if (p->m_left != NULL && p->m_right != NULL){parent = p;st.push(parent);q = p->m_left;while (q->m_right != NULL){parent = q;st.push(parent);q = q->m_right;}//替换p->m_value = q->m_value;p = q;}if (p->m_left != NULL)q = p->m_left;elseq = p->m_right;int f; //标记删除的是左孩子0，右孩子1if (parent == NULL)m_root = parent;else{if (parent->m_left == p){parent->m_left = q;f = 0;}else{parent->m_right = q;f = 1;}//删除完后调整bf//根据栈中存储的路径计算bfint link;while (!st.empty()){parent = st.top();st.pop();if (parent->m_right == q && f == 1)parent->m_bf--;elseparent->m_bf++;if (!st.empty()){//保存旋转之前的父节点，为了旋转后链接ppr = st.top();link = (ppr->m_left == parent) ? -1 : 1;}elselink = 0;if (parent->m_bf == -1 || parent->m_bf == 1)break;if (parent->m_bf == 0)q = parent;else{//旋转int flag = 0;if (parent->m_bf < 0){flag = -1;q = parent->m_left;}else{flag = 1;q = parent->m_right;}if (q->m_bf == 0)//单{if (flag == -1)//左高{RotateRR(parent);parent->m_bf = 1;parent->m_right->m_bf = -1;}else{RotateLL(parent);parent->m_bf = -1;parent->m_left->m_bf = 1;}break;}if (q->m_bf == flag){if (flag == -1)RotateRR(parent);elseRotateLL(parent);}else{if (flag == -1)RotateLR(parent);elseRotateRL(parent);}if (link == -1)ppr->m_left = parent;else if (link == 1)ppr->m_right = parent;}}if (st.empty())m_root = parent;}delete p;p = NULL;
}

写个简单的中序遍历，用来打印测试一下，因为bst树中序是从小到大排序的，那avl中序必然也是有序的

void AVLTree::TTer(AVLNode*& cur) {if (cur == nullptr)return;TTer(cur->m_left);cout << cur->m_value << " " ;TTer(cur->m_right);
}

写个测试：

int  main()
{vector<int>nums{ 3,2,1,4,5,6,7,10,9,8 };AVLTree t;for (const auto& x : nums){t.InsertAVLTree(x);//插入}t.TTer(t.m_root);//写个中序 遍历出来从小到大t.DelAVLTree(5);//删除个5cout << endl;t.TTer(t.m_root);return 0;
}