AVL树
一、AVL树
(一)概念
二叉搜索树虽可以缩短查找的效率,但如果数据有序或接近有序二叉搜索树将退化为单支树,查
找元素相当于在顺序表中搜索元素,效率低下。因此,两位俄罗斯的数学家G.M.Adelson-Velskii 和E.M.Landis在1962年发明了一种解决上述问题的方法:当向二叉搜索树中插入新结点后,如果能保证每个结点的左右 子树高度之差的绝对值不超过1(需要对树中的结点进行调整),即可降低树的高度,从而减少平均搜索长度。
一棵AVL树或者是空树,或者是具有以下性质的二叉搜索树:
1.它的左右子树都是AVL树
2.左右子树高度之差(简称平衡因子, 假定右减左)的绝对值不超过1(-1/0/1)
问: 为什么左右子树的高度差不能只设置成0?
答: 在只有两个节点的情况下,无法使得两棵树的子树平衡因子都为0.
补: 树的平衡因子不是必须要的,但是在这里我们用平衡因子来控制树.
(二)定义
如下定义一个AVL树节点的定义,这里我们是用的一个三叉树。
template<class K, class V>
struct AVLTreeNode {
AVLTreeNode<K, V>* _left;
AVLTreeNode<K, V>* _right;
AVLTreeNode<K, V>* _parent;
int bf;
pair<K, V> _kv;
AVLTreeNode(const pair<K, V> kv)
:_left(nullptr)
, _right(nullptr)
, _parent(nullptr)
, _bf(0)
, _kv(kv)
{}
};
二、AVL树的插入
AVL树就是在二叉搜索树的基础上引入了平衡因子,因此AVL树也可以看成是二叉搜索树。那么 AVL树的插入过程可以分为两步: 1. 按照二叉搜索树的方式插入新节点 2. 调整节点的平衡因子
template<class K, class V>
struct AVLTree {
typedef AVLTreeNode<K, V> Node;
public:
bool Insert(const pair<K, V>& kv) {
//1. 按照二叉搜索树的方式插入新节点
//2. 调整节点的平衡因子
}
private:
Node* _root = nullptr;
};
(一)先按照二叉搜索树的规则将节点插入到AVL树中
bool Insert(const pair<K, V>& kv) {
//1. 按照二叉搜索树的方式插入新节点
//2. 调整节点的平衡因子
if (_root == nullptr) {
_root = new Node(kv);
return true;
}
Node* parent = nullptr;
Node* cur = _root;
while (cur) {
if (cur->_kv.first > kv.first) {
parent = cur;
cur = cur->_left;
}
else if (cur->_kv.first < kv.first) {
parent = cur;
cur = cur->_right;
}
else {
return false;
}
}
cur = new Node(kv);
if (parent->_kv.first > kv.first)
parent->_left = cur;
else
parent->_right = cur;
cur->_parent = parent;
}
(二)调节平衡因子
问: 插入节点回影响那些平衡因子呢?
答: 新增节点的部分祖先
更新原则: cur更新到root位置, 结束。
cur是p的左边,p->_bf--
cur是p的右边,p->_bf++
1.更新后,p->_bf == 0,p所在的子树高度不变,不会影响爷爷,说明更新前,p的_bf是1或者-1
p在矮的节点那边插入了节点,左右均衡了,p的高度不变,不会影响爷爷.
2.更新后,p->_bf == 1 / -1,p所在的子树的高度变了,会影响爷爷,说明更新前,p的_bf是0
p的有一边插入,p变的不均衡,但是不违反规则,p的高度变了,会影响爷爷.
3.更新后p->_bf == 2 / -2,说明p所在的子树违反了平衡规则,需要进行处理->旋转
(让p所在子树高度回到插入之前,不会对上层的bf有影响)
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 = cur->_parent;
parent = parent->_parent;
}
else if (parent->_bf == 2 || parent->_bf == -2) {
// 旋转
}
else
assert(false);
}
(三)旋转
1.左旋转(当右边一条直线且bf == 2)
void RotateL(Node* parent) {
Node* subR = parent->_right; // parent的右节点
Node* subRL = subR->_left; // parent的右节点的左节点
parent->_right = subRL;
if (subRL) // 判断subRL不为空
subRL->_parent = parent;
subR->_left = parent;
Node ppnode = parent->_parent; // parent的父亲节点来判断subR的父亲节点
parent->_parent = subR;
if (parent == _root) {
_root = subR;
subR->_parent = nullptr;
}
else {
if (parent == ppnode->_left)
ppnode->_left = subR;
else
ppnode->_right = subR;
subR->_parent = ppnode;
}
parent->_bf = 0;
subR->_bf = 0;
}
2.右旋转(类似左旋转,左边一条直线且bf=-2)
void RotateR(Node* parent) {
Node* subL = parent->_left;//parent的左节点
Node* subLR = subL->_right;//parent的左节点的右节点
parent->_left = subLR;
if (subLR)
subLR->_parent = parent;
subL->_right = parent;
Node* ppnode = parent->_parent; //parent的父亲节点来判断subL的父亲节点
parent->_parent = subL;
if (parent == _root) { // 判断subL是否更新为根节点
_root = subL;
subL->_parent = nullptr;
}
else {
if (ppnode->_left == parent)
ppnode->_left = subL;
else
ppnode->_right = subL;
subL->_parent = ppnode;
}
parent->_bf = 0;
subL->_bf = 0;
}
3.左右旋转(先往左走,再往右走。一个bf为-2,一个bf为1。先左旋,再右旋,难点在于调节平衡因子(关键在于画图))
void RotateLR(Node* parent) {
Node* subL = parent->_left;
Node* subLR = subL->_right;
int bf = subLR->_bf;
RotateL(parent->_left);
RotateR(parent);
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 if (bf == 0) {
subLR->_bf = 0;
subL->_bf = 0;
parent->_bf = 0;
}
else
assert(false);
}
4.右左旋转(先往右走,再往左走。一个bf为2,一个bf为-1。先右旋,再左旋,难点在于调节平衡因子(关键在于画图))
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->_bf = 0;
subR->_bf = 1;
parent->_bf = 0;
}
else if (bf == 1) {
subRL->_bf = 0;
subR->_bf = 0;
parent->_bf = -1;
}
else if (bf == 0) { // 只有3个节点的情况
subRL->_bf = 0;
subR->_bf = 0;
parent->_bf = 0;
}
else
assert(false);
}
旋转代码:
if (parent->_bf == 2 && cur->_bf == 1)
RotateL(parent);
else if (parent->_bf == -2 && cur->_bf == -1)
RotateR(parent);
else if (parent->_bf == -2 && cur->_bf == 1)
RotateLR(parent);
else
RotateRL(parent);
break;
5.验证是否为AVL树:
bool _IsBalance(Node* root, int& height) {
if (root == nullptr) {
height = 0;
return true;
}
int LeftHeight = 0, RightHeight = 0;
if (!_IsBalance(root->_left, LeftHeight) ||
!_IsBalance(root->_right, RightHeight)) {
return false;
}
if (abs(LeftHeight - RightHeight) >= 2) {
cout << root->_kv.first << "不平衡" << endl;
return false;
}
if (RightHeight - LeftHeight != root->_bf) {
cout << root->_kv.first << "平衡英子异常" << endl;
return false;
}
height = max(LeftHeight, RightHeight) + 1;
return true;
}
bool IsBalance() {
int height = 0;
return _IsBalance(_root, height);
}
代码汇总:
#pragma once
#include <iostream>
#include <vector>
#include <assert.h>
using namespace std;
template<class K, class V>
struct AVLTreeNode {
AVLTreeNode<K, V>* _left;
AVLTreeNode<K, V>* _right;
AVLTreeNode<K, V>* _parent;
int _bf;
pair<K, V> _kv;
AVLTreeNode(const pair<K, V> kv)
:_left(nullptr)
, _right(nullptr)
, _parent(nullptr)
, _bf(0)
, _kv(kv)
{}
};
template<class K, class V>
struct AVLTree {
typedef AVLTreeNode<K, V> Node;
public:
bool Insert(const pair<K, V>& kv) {
//1. 按照二叉搜索树的方式插入新节点
//2. 调整节点的平衡因子
if (_root == nullptr) {
_root = new Node(kv);
return true;
}
Node* parent = nullptr;
Node* cur = _root;
while (cur) {
if (cur->_kv.first > kv.first) {
parent = cur;
cur = cur->_left;
}
else if (cur->_kv.first < kv.first) {
parent = cur;
cur = cur->_right;
}
else {
return false;
}
}
cur = new Node(kv);
if (parent->_kv.first > kv.first)
parent->_left = cur;
else
parent->_right = cur;
cur->_parent = parent;
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 = cur->_parent;
parent = parent->_parent;
}
else if (parent->_bf == 2 || parent->_bf == -2) {
// 旋转
if (parent->_bf == 2 && cur->_bf == 1)
RotateL(parent);
else if (parent->_bf == -2 && cur->_bf == -1)
RotateR(parent);
else if (parent->_bf == -2 && cur->_bf == 1)
RotateLR(parent);
else
RotateRL(parent);
break;
}
else
assert(false);
}
}
void RotateL(Node* parent) {
Node* subR = parent->_right; // parent的右节点
Node* subRL = subR->_left; // parent的右节点的左节点
parent->_right = subRL;
if (subRL) // 判断subRL不为空
subRL->_parent = parent;
subR->_left = parent;
Node* ppnode = parent->_parent; // parent的父亲节点来判断subR的父亲节点
parent->_parent = subR;
if (parent == _root) {
_root = subR;
subR->_parent = nullptr;
}
else {
if (parent == ppnode->_left)
ppnode->_left = subR;
else
ppnode->_right = subR;
subR->_parent = ppnode;
}
parent->_bf = 0;
subR->_bf = 0;
}
void RotateR(Node* parent) {
Node* subL = parent->_left;//parent的左节点
Node* subLR = subL->_right;//parent的左节点的右节点
parent->_left = subLR;
if (subLR)
subLR->_parent = parent;
subL->_right = parent;
Node* ppnode = parent->_parent; //parent的父亲节点来判断subL的父亲节点
parent->_parent = subL;
if (parent == _root) { // 判断subL是否更新为根节点
_root = subL;
subL->_parent = nullptr;
}
else {
if (ppnode->_left == parent)
ppnode->_left = subL;
else
ppnode->_right = subL;
subL->_parent = ppnode;
}
parent->_bf = 0;
subL->_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 == -1) {
subLR->_bf = 0;
subL->_bf = 0;
parent->_bf = 1;
}
else if (bf == 1) {
subLR->_bf = 0;
subL->_bf = -1;
parent->_bf = 0;
}
else if (bf == 0) {
subLR->_bf = 0;
subL->_bf = 0;
parent->_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->_bf = 0;
subR->_bf = 1;
parent->_bf = 0;
}
else if (bf == 1) {
subRL->_bf = 0;
subR->_bf = 0;
parent->_bf = -1;
}
else if (bf == 0) { // 只有3个节点的情况
subRL->_bf = 0;
subR->_bf = 0;
parent->_bf = 0;
}
else
assert(false);
}
bool _IsBalance(Node* root, int& height) {
if (root == nullptr) {
height = 0;
return true;
}
int LeftHeight = 0, RightHeight = 0;
if (!_IsBalance(root->_left, LeftHeight) ||
!_IsBalance(root->_right, RightHeight)) {
return false;
}
if (abs(LeftHeight - RightHeight) >= 2) {
cout << root->_kv.first << "不平衡" << endl;
return false;
}
if (RightHeight - LeftHeight != root->_bf) {
cout << root->_kv.first << "平衡英子异常" << endl;
return false;
}
height = max(LeftHeight, RightHeight) + 1;
return true;
}
bool IsBalance() {
int height = 0;
return _IsBalance(_root, height);
}
private:
Node* _root = nullptr;
};
void TestAVLTree()
{
const int N = 1000000;
vector<int> v;
v.reserve(N);
srand(time(0));
for (size_t i = 0; i < N; i++)
{
v.push_back(rand() + i);
//cout << v.back() << endl;
}
AVLTree<int, int> t;
for (auto e : v)
{
t.Insert(make_pair(e, e));
//cout << "Insert:" << e << "->" << t.IsBalance() << endl;
}
cout << t.IsBalance() << endl;
}