平衡搜索树-AVL树图文详解 (万字长文) - ToB企服应用市场:ToB评测及商务社交产业平台

template<class K, class V>
struct AVLTreeNode
{
//三叉链: left right parent
AVLTreeNode* _left; // 该节点的左孩子
AVLTreeNode* _right; // 该节点的右孩子
AVLTreeNode* _parent; // 该节点的双亲
std::pair<K,V> _kv; // 键值对
int _bf; // 该节点的平衡因子 balance factor
AVLTreeNode(const std::pair<K, V>& kv)
:_left(nullptr)
, _right(nullptr)
, _parent(nullptr)
, _kv(kv)
, _bf(0)
{}
};

复制代码

（可能会发生旋转的子树至少两个结点以上）

复制代码

//1. 右右
void RotateL(Node* parent) {
//. 记录爷爷(父亲的父亲)
//. 我是父的右儿子(我是主角)
//. 记录下我的左子树(托管)
// 旋转(爷、父、子关系重新调整）
// 成为爷爷的右儿子 (如果没有爷爷,则跳过;且说明父是根,更新我成为根)
// 把我的左子树托管给父成为他的右孩子
// 旧父成为我的左儿子,旧父的父更新成我
//. 更新平衡因子
//. 记录爷爷(父亲的父亲)
//. 我是父的右儿子
//. 记录下我的左子树
Node* pparent = parent->_parent;
Node* cur = parent->_right;
Node* leftchild = cur->_left;
//旋转
//. 成为爷爷的右儿子 (如果没有爷爷,则跳过;且说明父是根,更新我成为根)
if (pparent) { //有爷爷
if(parent == pparent->_left)
pparent->_left = cur;
else {
pparent->_right = cur;
}
cur->_parent = pparent; //三叉链维护
}
else { //没有爷爷,父亲是根
cur->_parent = nullptr;
_root = cur;
}
//. 父子地位交换
parent->_right = leftchild;
if (leftchild) { //三叉链维护
leftchild->_parent = parent;
}
cur->_left = parent;
parent->_parent = cur;
//旋转【end】
//更新平衡因子
cur->_bf = 0;
parent->_bf = 0;
}
//2. 左左
void RotateR(Node* parent) {
//. 记录爷爷
//. 我是父的左儿子
//. 记录下我的右子树
Node* pparent = parent->_parent;
Node* cur = parent->_left;
Node* rightChild = cur->_right;
//旋转
//. 成为爷爷的左儿子 (如果没有爷爷,则跳过;且说明父是根,更新我成为根)
if (pparent) { //有爷爷
if (parent == pparent->_left)
pparent->_left = cur;
else {
pparent->_right = cur;
}
cur->_parent = pparent; //三叉链维护
}
else { //没有爷爷,父亲是根
cur->_parent = nullptr;
_root = cur;
}
//. 父子地位交换
parent->_left = rightChild;
if (rightChild) { //三叉链维护
rightChild->_parent = parent;
}
cur->_right = parent;
parent->_parent = cur;
//旋转【end】
//更新平衡因子
cur->_bf = 0;
parent->_bf = 0;
}
//3. 左右
void RotateLR(Node* parent) {
//我是儿子,但是主角是孙子
//记录下孙子
//记录下孙子的平衡因子(特征)
//对孙子进行左单旋,再右旋
//更新平衡因子
Node* cur = parent->_left;
Node* grandson = cur->_right;
int bf = grandson->_bf;
RotateL(cur);
RotateR(grandson->_parent);
//三种情况
if (bf == 0) {
parent->_bf = 0;
cur->_bf = 0;
grandson->_bf = 0;
}
else if (bf == 1) {
parent->_bf = 0;
cur->_bf = -1;
grandson->_bf = 0;
}
else if (bf == -1) {
parent->_bf = 1;
cur->_bf = 0;
grandson->_bf = 0;
}
else {
assert(false); //错误检查
}
}
//4. 右左
void RotateRL(Node* parent) {
//我是儿子(父的右孩子),但是主角是孙子
//记录下孙子(我的左孩子)
//记录下孙子的平衡因子(特征)
//对孙子进行右单旋,再左单旋
//更新平衡因子
Node* cur = parent->_right;
Node* grandson = cur->_left;
int bf = grandson->_bf;
RotateR(cur); //将孙子的爹,就是我,进行右单旋
RotateL(grandson->_parent); //将儿子的新爹进行左单旋
//三种情况
if (bf == 0) {
parent->_bf = 0;
cur->_bf = 0;
grandson->_bf = 0;
}
else if (bf == 1) {
parent->_bf = -1;
cur->_bf = 0;
grandson->_bf = 0;
}
else if (bf == -1) {
parent->_bf = 0;
cur->_bf = 1;
grandson->_bf = 0;
}
else {
assert(false);
}
}

复制代码

bool Insert(const std::pair<K,V> kv) {
//第一个结点做根
if (_root == nullptr) {
_root = new Node(kv);
_size++;
return true;
}
//搜索
Node* parent = _root;
Node* cur = _root;
while (cur) {
//大于往右走
if (kv.first > cur->_kv.first) {
parent = cur;
cur = cur->_right;
}
//小于往左走
else if (kv.first < cur->_kv.first) {
parent = cur;
cur = cur->_left;
}
//找到了,存在相同的key
else {
return false;
}
} //循环搜索...
//不存在,可以插入
cur = new Node(kv); //new后,cur值发生改变,之后都不能使用地址进行比较
if (cur->_kv.first < parent->_kv.first) {
parent->_left = cur;
}
else {
parent->_right = cur;
}
cur->_parent = parent; //三叉链链上父结点
_size++;
//调整平衡因子 : 最多到根,根的parent为nullptr
while (parent) {
//更新平衡因子
if (cur->_kv.first < parent->_kv.first) {
parent->_bf--;
}
else {
parent->_bf++;
}
//看是否需要调整
if (parent->_bf == 1 || parent->_bf == -1) {
cur = parent;
parent = parent->_parent;
}
else if(parent->_bf == 0){
break;
}
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;
}

复制代码

size_t Hight() {
return _Hight(_root);
}
bool IsBalance() {
return _IsBalance(_root);
}
size_t _Hight(Node* root) {
if (root == 0) return 0; //空
size_t leftH = _Hight(root->_left);
size_t rightH = _Hight(root->_right);
return std::max(leftH, rightH) + 1; //+1:自己高度为1
}
bool _IsBalance(Node* root) {
if (root == nullptr) return true;
int leftH = _Hight(root->_left);
int rightH = _Hight(root->_right);
int bf = rightH-leftH;
return bf == root->_bf //平衡因子
&& (bf > -2 && bf < 2) //高度差
&& _IsBalance(root->_left)
&& _IsBalance(root->_right);
}

复制代码