C++手撕AVL树
【摘要】 本文主要介绍AVL树，以及使用C++来实现它。
@[toc]
1.概念
(1)二叉搜索树的缺点
要手撕AVL树，我们首先要知道什么是AVL树。AVL树是在二叉搜索树的基础之上改造的。当我们插入的是一个有序的序列的时候，二叉搜素树会使用一条直线来进行存储，这样并不利于查找。
当遇到这种情况的时候我们就需要对这棵树来进行调整。AVL树会通过旋转等操作，来规避这种情况。最终满足每一个节点的平衡因子的绝对值<=1，从而达到近似平衡的目的。
节点的平衡因子值=右子树的高度-左子树高度
(2)定义节点
在AVL树中，除了需要定义平衡因子bf之外，还需要定义指向节点父节点的指针。方便我们来进行平衡因子的更新。
struct AVLTreeNode
{
AVLTreeNode* right;
AVLTreeNode* left;
AVLTreeNode* parent;
pair<int, int> _kv;
int _bf;
AVLTreeNode(pair<int, int> kv)
:right(nullptr)
,left(nullptr)
,parent(nullptr)
,_kv(kv)
,_bf(0)
{}
};
同时和map一样，我们使用pair类型来进行数据的存储。
2.插入
(1)拆分
AVL树的插入就是AVL树的精髓所在，我们在插入节点的同时还需要对平衡因子进行控制。
AVL树的插入我们可以拆分成五个函数，其中四个为旋转函数，一个为主要的插入函数。
而这个主要的插入函数，我们还可以将其分为三个部分：找节点，插节点，更新平衡因子。而更新平衡因子后就需要判断是否需要进行旋转的操作。
在进行插入之前，我们将插入的节点定义为kv。
(2)找节点与插节点
这一过程与二叉搜索树是相同的，这里就不多赘述了。二叉搜索树
直接上代码：
//初始化头结点
if (_root == nullptr)
{
_root = new Node(kv);
return true;
}
//找到要插入节点的位置
Node* cur = _root;
Node* parent = nullptr;
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
{
assert(false);
}
}
//插入节点
cur = new Node(kv);
if (parent->_kv.first<kv.first)
{
parent->right = cur;
cur->parent = parent;
}
else if (parent->_kv.first>kv.first)
{
parent->left = cur;
cur->parent = parent;
}
else
{
assert(false);
}
(3)更新平衡因子与旋转
更新平衡因子
每当我们插入一个节点的时候，就需要对该节点的所有父辈节点来进行平衡因子的更新。注意，当插入节点后，只有其父辈节点的平衡因子才会受到影响，而其他节点的平衡因子不会被影响。
可以根据每个节点的parent来找到其父亲节点，从而逐渐向上更新平衡因子。
当遇到以下两种情况平衡因子的更新停止。
1.某一父辈节点的平衡因子为0。
2.更新到根节点。
旋转
当更新之后的平衡因子为2或者-2的时候，不符合AVL树的平衡因子在-1~1之间的定义，此时需要发生旋转。触发旋转的条件与当前节点cur和它的parent有关。
当parent和cur的平衡因子分别为：
(1)2和1，触发左旋
void RotateL(Node* parent)
{
Node* cur = parent->right;
Node* curL = cur->left;
Node* parentParent = parent->parent;
parent->right = curL;
if (curL)
curL->parent = parent;
cur->left = parent;
parent->parent = cur;
if (parent == _root)
{
_root = cur;
_root->parent = nullptr;
}
else
{
if (parentParent->left == parent)
{
parentParent->left = cur;
cur->parent = parentParent;
}
else if (parentParent->right == parent)
{
parentParent->right = cur;
cur->parent = parentParent;
}
else
{
assert(false);
}
}
parent->_bf = 0;
cur->_bf = 0;
}
用一张图来表示一下这个过程：
h表示某树的高度，当在红色部分处插入一个节点时，60的平衡因子变为1，30的平衡因子变为2。
此时就需要发生旋转：
通过旋转使树重新变成一棵AVL树，整个过程分为三步：
1.60的左子树置为30,30的右子树置为60的左子树。
2.将30与更上层的父辈节点链接起来。
3.将30和60的平衡因子都更新为0。
注意，由于AVL树是三叉树，因此在链接的时候需要将父节点也链接起来。因此在将60的左子树链接到30的右子树的时候，需要进行判空来避免空指针的解引用：
void RotateL(Node* parent)
{
Node* cur = parent->right;
Node* curL = cur->left;
Node* parentParent = parent->parent;
parent->right = curL;
if (curL)
curL->parent = parent;
cur->left = parent;
parent->parent = cur;
if (parent == _root)
{
_root = cur;
_root->parent = nullptr;
}
else
{
if (parentParent->left == parent)
{
parentParent->left = cur;
cur->parent = parentParent;
}
else if (parentParent->right == parent)
{
parentParent->right = cur;
cur->parent = parentParent;
}
else
{
assert(false);
}
}
parent->_bf = 0;
cur->_bf = 0;
}
(2)-2和-1，触发右旋
右旋同样分为两步：
1.将30的右链接到60的左子树。将60链接到30的右。
2.将30与上层节点链接起来。
3.将30和60的平衡因子都更新为0。
void RotateR(Node* parent)
{
Node* cur = parent->left;
Node* curL = cur->left;
Node* curR = cur->right;
Node* parentParent = parent->parent;
parent->left = curR;
if (curR)
curR->parent = parent;
cur->right = parent;
parent->parent = cur;
if (parent == _root)
{
_root = cur;
_root->parent = nullptr;
}
else
{
if (parentParent->left == parent)
{
parentParent->left = cur;
cur->parent = parentParent;
}
else if (parentParent->right == parent)
{
parentParent->right = cur;
cur->parent = parentParent;
}
else
{
assert(false);
}
}
cur->_bf = 0;
parent->_bf = 0;
}
(3)-2和1，左右双旋
当为-2和1或者2和-1的时候，仅仅靠单旋是解决不了问题的，这个时候我们就需要进行双旋：
左单旋：
右单旋：
无论是在红色部分或者蓝色部分插入节点，都会导致发生左右双旋。
左右双旋分为三步：
1.对30节点进行左单旋。
2.对90节点进行右单旋。
3.根据60的平衡因子来更新30和90的平衡因子：当60的平衡因子为0时，30和90的平衡因子也为0；当60的平衡因子为1时，30的平衡因子为-1，90的平衡因子为0；当60的平衡因子为-1时，30的平衡因子为0,90的平衡因子为1。
void RotateLR(Node* parent)
{
Node* subL = parent->left;
Node* subLR =subL->right;
int bf = subLR->_bf;
RotateL(parent->left);
RotateR(parent);
if (bf == 0)
{
parent->_bf = 0;
subLR->_bf = 0;
subLR->_bf = 0;
}
else if (bf == -1)
{
parent->_bf = 1;
subL->_bf = 0;
subLR->_bf = 0;
}
else if (bf == 1)
{
parent->_bf = 0;
subL->_bf = -1;
subLR->_bf = 0;
}
}
(4)2和-1，右左双旋
右单旋：
左单旋：
无论是在红色部分或者蓝色部分插入节点，都会导致发生右左双旋。
右左双旋分为三步：
1.对90节点进行右单旋。
2.对30节点进行左单旋。
3.根据60的平衡因子来更新30和90的平衡因子：当60的平衡因子为0时，30和90的平衡因子也为0；当60的平衡因子为1时，30的平衡因子为-1，90的平衡因子为0；当60的平衡因子为-1时，30的平衡因子为0,90的平衡因子为1。
void RotateRL(Node* parent)
{
Node* subR = parent->right;
Node* subRL = subR->left;
int bf = subRL->_bf;
RotateR(parent->right);
RotateL(parent);
if (bf == 0)
{
parent->_bf = 0;
subR->_bf = 0;
subRL->_bf = 0;
}
else if (bf == 1)
{
parent->_bf = -1;
subR->_bf = 0;
subRL->_bf = 0;
}
else if (bf == -1)
{
parent->_bf = 0;
subR->_bf = 1;
subRL->_bf = 0;
}
else
{
assert(false);
}
}
3.判断
我们可以建立一个函数来判断一棵树是否为AVL树。
我们使用递归来进行这一过程，依次判断各个子树是否为AVL树。
要判断我们就需要知道每一棵树的高度，此时我们需要构造一个求树的高度的函数Height。它也由递归来实现。
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;
}
bool IsBalance()
{
return _IsBalance(_root);
}
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->_bf << endl;
cout << "应该是：" << rightHeight - leftHeight << endl;
return false;
}
return abs(rightHeight - leftHeight) < 2 && _IsBalance(root->left) && _IsBalance(root->right);
}
4.完整代码及测试代码
完整代码：
#pragma once
#include<iostream>
#include<assert.h>
#include<math.h>
using namespace std;
struct AVLTreeNode
{
AVLTreeNode* right;
AVLTreeNode* left;
AVLTreeNode* parent;
pair<int, int> _kv;
int _bf;
AVLTreeNode(pair<int, int> kv)
:right(nullptr)
,left(nullptr)
,parent(nullptr)
,_kv(kv)
,_bf(0)
{}
};
class AVLTree
{
typedef AVLTreeNode Node;
public:
AVLTree()
{
_root = nullptr;
}
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);
}
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;
}
bool IsBalance()
{
return _IsBalance(_root);
}
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->_bf << endl;
cout << "应该是：" << rightHeight - leftHeight << endl;
return false;
}
return abs(rightHeight - leftHeight) < 2 && _IsBalance(root->left) && _IsBalance(root->right);
}
//右单旋
void RotateR(Node* parent)
{
Node* cur = parent->left;
Node* curL = cur->left;
Node* curR = cur->right;
Node* parentParent = parent->parent;
parent->left = curR;
if (curR)
curR->parent = parent;
cur->right = parent;
parent->parent = cur;
if (parent == _root)
{
_root = cur;
_root->parent = nullptr;
}
else
{
if (parentParent->left == parent)
{
parentParent->left = cur;
cur->parent = parentParent;
}
else if (parentParent->right == parent)
{
parentParent->right = cur;
cur->parent = parentParent;
}
else
{
assert(false);
}
}
cur->_bf = 0;
parent->_bf = 0;
}
//左单旋
void RotateL(Node* parent)
{
Node* cur = parent->right;
Node* curL = cur->left;
Node* parentParent = parent->parent;
parent->right = curL;
if (curL)
curL->parent = parent;
cur->left = parent;
parent->parent = cur;
if (parent == _root)
{
_root = cur;
_root->parent = nullptr;
}
else
{
if (parentParent->left == parent)
{
parentParent->left = cur;
cur->parent = parentParent;
}
else if (parentParent->right == parent)
{
parentParent->right = cur;
cur->parent = parentParent;
}
else
{
assert(false);
}
}
parent->_bf = 0;
cur->_bf = 0;
}
//左右双旋
void RotateLR(Node* parent)
{
Node* subL = parent->left;
Node* subLR =subL->right;
int bf = subLR->_bf;
RotateL(parent->left);
RotateR(parent);
if (bf == 0)
{
parent->_bf = 0;
subLR->_bf = 0;
subLR->_bf = 0;
}
else if (bf == -1)
{
parent->_bf = 1;
subL->_bf = 0;
subLR->_bf = 0;
}
else if (bf == 1)
{
parent->_bf = 0;
subL->_bf = -1;
subLR->_bf = 0;
}
}
//右左双旋
void RotateRL(Node* parent)
{
Node* subR = parent->right;
Node* subRL = subR->left;
int bf = subRL->_bf;
RotateR(parent->right);
RotateL(parent);
if (bf == 0)
{
parent->_bf = 0;
subR->_bf = 0;
subRL->_bf = 0;
}
else if (bf == 1)
{
parent->_bf = -1;
subR->_bf = 0;
subRL->_bf = 0;
}
else if (bf == -1)
{
parent->_bf = 0;
subR->_bf = 1;
subRL->_bf = 0;
}
else
{
assert(false);
}
}
bool InsertNode(pair<int, int> kv)
{
//初始化头结点
if (_root == nullptr)
{
_root = new Node(kv);
return true;
}
//找到要插入节点的位置
Node* cur = _root;
Node* parent = nullptr;
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
{
assert(false);
}
}
//插入节点
cur = new Node(kv);
if (parent->_kv.first<kv.first)
{
parent->right = cur;
cur->parent = parent;
}
else if (parent->_kv.first>kv.first)
{
parent->left = cur;
cur->parent = parent;
}
else
{
assert(false);
}
//更新插入节点以上的平衡因子
while (parent)
{
if (cur == parent->left)
{
parent->_bf--;
}
else if (cur == parent->right)
{
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);
}
}
}
private:
Node* _root;
};
测试代码：
#define _CRT_SECURE_NO_WARNINGS 1
#include"AVLTree.h"
void TestRotateR()
{
AVLTree t;
t.InsertNode(make_pair(5, 1));
t.InsertNode(make_pair(4, 1));
t.InsertNode(make_pair(3, 1));
t.InsertNode(make_pair(2, 1));
t.InsertNode(make_pair(1, 1));
t.InsertNode(make_pair(0, 1));
t.InOrder();
cout << t.IsBalance() << endl;
}
void TestRotateL()
{
AVLTree t;
t.InsertNode(make_pair(0, 1));
t.InsertNode(make_pair(1, 1));
t.InsertNode(make_pair(2, 1));
t.InsertNode(make_pair(3, 1));
t.InsertNode(make_pair(4, 1));
t.InsertNode(make_pair(5, 1));
t.InOrder();
cout << t.IsBalance() << endl;
}
void Testbf()
{
AVLTree t;
t.InsertNode(make_pair(5, 1));
t.InsertNode(make_pair(7, 1));
t.InsertNode(make_pair(3, 1));
t.InsertNode(make_pair(4, 1));
t.InsertNode(make_pair(2, 1));
t.InsertNode(make_pair(8, 1));
t.InsertNode(make_pair(9, 1));
t.InsertNode(make_pair(6, 1));
t.InsertNode(make_pair(1, 1));
t.InsertNode(make_pair(11, 1));
t.InOrder();
cout << t.IsBalance() << endl;
}
void TestRL()
{
AVLTree t;
t.InsertNode(make_pair(60, 1));
t.InsertNode(make_pair(50, 1));
t.InsertNode(make_pair(90, 1));
t.InsertNode(make_pair(100, 1));
t.InsertNode(make_pair(80, 1));
t.InsertNode(make_pair(70, 1));
t.InOrder();
cout << t.IsBalance() << endl;
}
void TestLR()
{
AVLTree t;
t.InsertNode(make_pair(90, 1));
t.InsertNode(make_pair(100, 1));
t.InsertNode(make_pair(60, 1));
t.InsertNode(make_pair(50, 1));
t.InsertNode(make_pair(70, 1));
t.InsertNode(make_pair(80, 1));
t.InOrder();
cout << t.IsBalance() << endl;
}
int main()
{
//TestRotateR();
//Testbf();
//TestRotateL();
//TestRL();
TestLR();
}
【版权声明】本文为华为云社区用户原创内容，转载时必须标注文章的来源（华为云社区）、文章链接、文章作者等基本信息， 否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容，举报邮箱：
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论（0）