文章目录

AVL树的简单介绍全部的实现代码放在了文章末尾准备工作包含头文件类的成员变量

构造函数和拷贝构造swap和赋值运算符重载析构函数findinsert[重要]当parent的平衡因子为1/-1时，如何向上更新祖先节点的平衡因子呢？怎么旋转？左单旋右单旋左右双旋右左双旋

旋转的平衡因子更新左单旋和右单旋左右双旋和右左双旋

insert的全部代码

emptysize中序遍历全部代码

AVL树的简单介绍

我上一篇文章提到的普通二叉搜索树虽可以缩短查找的效率，但如果数据有序或接近有序二叉搜索树将退化为单支树，查找元素相当于在顺序表中搜索元素，效率低下。

AVL树就可以解决上述问题，让搜索树的查找效率在任何情况下都能稳定是<code>O(logN)

AVL树解决上述问题的方法是：

保证每个结点的左右子树高度之差的绝对值不超过1

这样就能保证树中的节点分布接近满二叉树，高度非常接近logN【N为树中节点的个数】，进而让一次查找的效率为O(logN)

为什么是保证每个结点的左右子树高度之差的绝对值不超过1，而不是保证左右子树高度一样呢？

其实很简单：

因为在一些情况下绝对不可能做到左右子树高度一样，例如：

此时无论如何改变树的形态，都不可能做到每个结点的左右子树高度相等

---

综上：

一棵AVL树或者是空树，或者是具有以下性质的<code>二叉搜索树：

它的左右子树都是AVL树左右子树高度之差(简称平衡因子)的绝对值不超过1

---

全部的实现代码放在了文章末尾

准备工作

创建两个文件，一个头文件AVLTree.hpp，一个源文件test.cpp

【因为模板的声明和定义不能分处于不同的文件中，所以把成员函数的声明和定义放在了同一个文件AVLTree.hpp中】

AVLTee.hpp：存放包含的头文件，命名空间的定义，成员函数和命名空间中的函数的定义

test.cpp：存放main函数，以及测试代码

---

包含头文件

iostream：用于输入输出cmath:提供数学函数

---

类的成员变量

实现AVL树最主要的就是保证树中节点的左右子树高度差不超过1

而维护这一条件的方法并不是唯一的，我使用的是平衡因子来维护

平衡因子时每个节点都有的，它的值就是这个节点的左右子树高度之差【一般是右子树高度-左子树高度】

---

构造函数和拷贝构造

构造函数没什么好说的，默认构造就行了

<code>AVLTree():_root(nullptr)

{ }

拷贝构造：

因为节点都是从堆区new出来的，所以要深拷贝

使用递归实现深拷贝：

因为拷贝构造不能有多余的参数，但是递归函数又必须使用参数记录信息

然后在拷贝构造里面调用一下这个函数就行了

<code>AVLTree(const AVLTree& obj)

{

根节点的父亲节点是nullptr

_root = Copy(obj._root,nullptr);

}

---

swap和赋值运算符重载

交换两颗二叉搜索树的本质就是交换两颗数的资源（数据），而它们的资源都是从堆区申请来的，然后用指针指向这些资源

<code>并不是把资源存储在了二叉搜索树对象中

所以资源交换很简单，直接交换_root指针的指向即可

void Swap(AVLTree& obj)

{

std::swap(_root, obj._root);

}

---

析构函数

使用递归遍历，把所有从堆区申请的节点都释放掉：

因为析构函数不能有多余的参数，但是递归函数又必须使用参数记录信息

所以再封装一个成员函数，专门用来递归释放：

然后在拷贝构造里面调用一下这个函数就行了

<code>~AVLTree()

{

Destroy(_root);

_root = nullptr;

}

---

find

具体流程：

从根节点开始，将目标值（传入的key）与当前节点的key进行比较。

如果目标值小于当前节点值，则在左子树中继续查找；

如果目标值大于当前节点值，则在右子树中继续查找。

这个过程一直进行，直到找到与目标值或者到达空节点为止。

把上述过程转成代码：

---

insert[重要]

AVL树就是在二叉搜索树的基础上引入了平衡因子，因此AVL树也可以看成是二叉搜索树。

那么AVL树的插入过程可以分为两步：

先按照二叉搜索树的方式插入新节点

再调整节点的平衡因子

因为新节点一定是插在<code>叶子节点或者只有一个孩子节点的节点上

所以插入节点后一定会影响新节点的父亲节点的平衡因子，可能会影响祖先节点

插入节点后具体分以下3种情况：

插入节点的父亲节点（以下简称parent）的平衡因子等于0

那么就说明插入之前parent的平衡因子一定是1/-1

所以parent在插入之前是只有一个孩子节点的节点

即以parent为根的子树插入之前的高度就是2，插入之后高度还是2

所以插入前后以parent为根的子树的高度没有改变，自然就不会影响parent的祖先的平衡因子

所以<code>不需要再向上取跟新祖先节点的平衡因子

直接插入结束

插入节点的父亲节点（以下简称parent）的平衡因子等于1/-1

那么就说明插入之前parent的平衡因子一定是0【如果插入前是2/-2的话，一定早就被旋转了】

所以parent在插入之前是叶子节点

即以parent为根的子树插入之前的高度就是1，插入之后高度就变成了2

所以插入前后以parent为根的子树的高度增加了，自然就会影响parent的祖先的平衡因子

所以<code>需要再向上继续更新祖先节点的平衡因子

插入节点的父亲节点（以下简称parent）的平衡因子等于2/-2 此时parent的左右子树高度差已经超过1，已经违反了AVL树的规则 需要旋转进行处理

---

当parent的平衡因子为1/-1时，如何向上更新祖先节点的平衡因子呢？

其实也简单：

就是把<code>原来的parent当做新的cur，把parent的父节点作为新的parent

再判断新的cur是父亲节点的左还是右，据此再更新新的parent的平衡因子

即

cur = parent;

parent = parent->_parent;

因为以之前的parent为根的子树，高度增加了1

右因为平衡因子=右子树高度-左子树高度

所以：

if (cur==parent->_left)

{

parent->_bf--;

}

else

{

parent->_bf++;

}

然后，再重复判断一下新的parent的平衡因子的3种情况，进行处理

新的parent的平衡因子变成了0,插入就结束新的parent的平衡因子变成了1/-1,就再重复这个过程，继续向上更新祖先节点的平衡因子新的parent的平衡因子变成了2/-2,就旋转

---

怎么旋转？

旋转分以下4种：

左单旋

所有的需要左单旋的情况，都可以画成下图的抽象图

具体情况描述：

插入前paernt的平衡因子为1，并且它的右边（PR）的平衡因子为0

新插入的节点<code>插在子树c上，并使子树c的高度增加1

插入后并向上跟新后：paernt的平衡因子变成2，并且它的右边（PR）的平衡因子变成了1

此时就使用左单旋：

把（下图中的）PRL链接在parent的右子树上，再把parent连接在PR的左子树上

把PR作为这颗子树新的根

这样就可以做到：在不违反搜索树规则【所有左子树上的值<根<右子树】的基础上，尽可能地让树平衡

将上述过程转换成代码：

---

右单旋

所有的需要右单旋的情况，都可以画成下图的抽象图

具体情况描述：

插入前paernt的平衡因子为-1，并且它的左边（PL）的平衡因子为0

新插入的节点<code>插在子树a上，并使子树a的高度增加1

插入后并向上跟新后：paernt的平衡因子变成-2，并且它的左边（PL）的平衡因子变成了-1

此时就使用左单旋：

把（下图中的）PLR链接在parent的左子树上，再把parent连接在PL的右子树上

把PL作为这颗子树新的根

这样就可以做到：在不违反搜索树规则【所有左子树上的值<根<右子树】的基础上，尽可能地让树平衡

将上述过程转换成代码：

---

左右双旋

所有的需要左右双旋的情况，都可以画成下图的抽象图

具体情况描述：

插入前paernt的平衡因子为<code>-1，并且它的左边（PL）的平衡因子为0

新插入的节点插在子树b或者c上，并使子树b或者c的高度增加1

插入后并向上跟新后：paernt的平衡因子变成-2，并且它的左边（PL）的平衡因子变成了1

此时使用一次单旋，是解决不了的，旋了之后还是有平衡因子为2/-2的节点

但是如果我们对PL进行左单旋之后，就可以发现可以对parent使用右旋来使树，在不违反搜索树规则【所有左子树上的值<根<右子树】的基础上，尽可能地接近平衡

即

RotateL(parent->_left);

RotateR(parent);

---

右左双旋

所有的需要右左双旋的情况，都可以画成下图的抽象图

具体情况描述：

插入前paernt的平衡因子为<code>1，并且它的右边（PR）的平衡因子为0

新插入的节点插在子树b或者c上，并使子树b或者c的高度增加1

插入后并向上跟新后：paernt的平衡因子变成2，并且它的右边（PR）的平衡因子变成了-1

此时使用一次单旋，是解决不了的，旋了之后还是有平衡因子为2/-2的节点

但是如果我们对PR进行右单旋之后，就可以发现可以对parent使用左单旋来使树，在不违反搜索树规则【所有左子树上的值<根<右子树】的基础上，尽可能地接近平衡

即

RotateR(parent->_right);

RotateL(parent);

---

旋转的平衡因子更新

左单旋和右单旋

因为插入的情况都只有一种，所以平衡因子的更新很简单，看上面画的示意图就行

即

parent和PR(PL)的平衡因子最后都变成0，其他节点的平衡因子没有变化

---

左右双旋和右左双旋

因为左右双旋和右左双旋的新节点既可以插在子树b上，又可以插在子树c上

而插在这两颗子树上的平衡因子更新是不同的

例

下图是左右双旋新节点插在子树b上的

最后：parent的平衡因子=1，PL的平衡因子=0，PLR的平衡因子=0

下图是左右双旋新节点插在<code>子树c上的

最后：parent的平衡因子=0，PL的平衡因子=-1，PLR的平衡因子=0

---

而且当h=0时，还有一种情况：

下图是左右双旋的h=0的旋转图

最后：parent的平衡因子=0，PL的平衡因子=0，PLR的平衡因子=0

---

综上：

<code>左右双旋代码

右左双旋同理

insert的全部代码

<code>bool Insert(const T& data)

{

if (_root == nullptr) 树为空，则直接新增节点

{

赋值给二叉搜索树的成员变量`_root`指针

_root = new Node(data);

return true; 返回true，代表插入成功

}

Node* cur = _root; 从根节点开始

定义parent来保存cur的父亲节点

假设根节点的父亲节点为nullptr

Node* parent = nullptr;

while (cur)

{

if (cur->_data < data） 目标值`大于`当前节点值，则在`右子树`中继续查找

{

parent = cur;

cur = cur->_right;

}

else if (cur->_data > data) 目标值'小于'当前节点值，则在'左子树'中继续查找

{

parent = cur;

cur = cur->_left;

}

else 已经有了一个节点的key与要插入的节点的key相等，就插入失败

{

return false; 插入失败返回false

}

}

Node* newnode = new Node(data); new出新节点

if (parent->_data > data) 比父亲节点小

{

parent->_left = newnode; 就连接到左边

平衡因子=右子树高度-左子树高度

所以 左 子树高度增加1，平衡因子 减小1

parent->_bf--;

}

else//比父亲节点大

{

parent->_right = newnode;就连接到右边

平衡因子=右子树高度-左子树高度

所以 右 子树高度增加1，平衡因子 增加1

parent->_bf++;

}

连接父亲节点

newnode->_parent = parent;

如果parent的平衡因子为1/-1

就向上更新

while (parent->_bf == 1||parent->_bf==-1)

{

cur = parent; 把原来的parent作为新的cur

parent = parent->_parent; 把原来的parent的父亲作为新的parent

if (parent == nullptr) 如果cur更新到根节点，就直接结束

return true;

因为平衡因子=右子树高度-左子树高度

所以

if (cur==parent->_left)

{

在左边

parent->_bf--; 平衡因子-=1

}

else

{

在右边

parent->_bf++;平衡因子+=1

}

}

if (parent->_bf == 2 || parent->_bf == -2) 需要旋转

{

if (parent->_bf == 2 && parent->_right->_bf == 1)左单旋

{

RotateL(parent);

}

else if (parent->_bf == -2 && parent->_left->_bf == -1)右单旋

{

RotateR(parent);

}

else if (parent->_bf == 2 && parent->_right->_bf == -1)右左双旋

{

RotateRL(parent);

}

else if (parent->_bf == -2 && parent->_left->_bf == 1)左右双旋

{

RotateLR(parent);

}

}

return true;

}

---

empty

bool Empty()

{

如果_root为空，那么树就是空的

return _root == nullptr;

}

---

size

使用递归实现二叉搜索树的节点个数统计：

因为我们经常使用的stl的容器的size都是没有参数的，但是递归函数又必须使用参数记录信息

所以再封装一个成员函数，专门用来递归：

然后再size里面调用一下就行了

<code>size_t Size()

{

return _Size(_root);

}

---

中序遍历

中序遍历的递归函数：

然后再调用递归函数

<code>void InOrder()

{

_InOrder(_root);

}

---

全部代码

#define _CRT_SECURE_NO_WARNINGS

#include<iostream>

#include<cmath>

using namespace std;

template<class T>

struct AVLTreeNode

{

T _data;

AVLTreeNode* _parent;

AVLTreeNode* _left;

AVLTreeNode* _right;

int _bf;

AVLTreeNode(const T& data=T())

:_data(data),

_parent(nullptr),

_left(nullptr),

_right(nullptr),

_bf(0)

{ }

};

template<class T>

class AVLTree

{

private:

typedef AVLTreeNode<T> Node;

Node* _root = nullptr;

public:

AVLTree():_root(nullptr)

{ }

AVLTree(const AVLTree& obj)

{

//根节点的父亲节点是nullptr

_root = Copy(obj._root,nullptr);

}

AVLTree& operator=(AVLTree obj)

{

this->Swap(obj);

return *this;

}

~AVLTree()

{

Destroy(_root);

_root = nullptr;

}

void Swap(AVLTree& obj)

{

std::swap(_root, obj._root);

}

bool Insert(const T& data)

{

if (_root == nullptr)//树为空，则直接新增节点

{

//赋值给二叉搜索树的成员变量`_root`指针

_root = new Node(data);

return true;//返回true，代表插入成功

}

Node* cur = _root;//从根节点开始

//定义parent来保存cur的父亲节点

//假设根节点的父亲节点为nullptr

Node* parent = nullptr;

while (cur)

{

if (cur->_data < data)//目标值`大于`当前节点值，则在`右子树`中继续查找

{

parent = cur;

cur = cur->_right;

}

else if (cur->_data > data)//目标值'小于'当前节点值，则在'左子树'中继续查找

{

parent = cur;

cur = cur->_left;

}

else//已经有了一个节点的key与要插入的节点的key相等，就插入失败

{

return false;//插入失败返回false

}

}

Node* newnode = new Node(data);//new出新节点

if (parent->_data > data)//比父亲节点小

{

parent->_left = newnode;//就连接到左边

//平衡因子=右子树高度-左子树高度

//

//所以 左 子树高度增加1，平衡因子 减小1

parent->_bf--;

}

else//比父亲节点大

{

parent->_right = newnode;//就连接到右边

//平衡因子=右子树高度-左子树高度

//

//所以 右 子树高度增加1，平衡因子 增加1

parent->_bf++;

}

//连接父亲节点

newnode->_parent = parent;

while (parent->_bf == 1||parent->_bf==-1)

{

cur = parent;

parent = parent->_parent;

if (parent == nullptr)

return true;

if (cur==parent->_left)

{

parent->_bf--;

}

else

{

parent->_bf++;

}

}

if (parent->_bf == 2 || parent->_bf == -2)//需要旋转

{

if (parent->_bf == 2 && parent->_right->_bf == 1)//左单旋

{

RotateL(parent);

}

else if (parent->_bf == -2 && parent->_left->_bf == -1)//右单旋

{

RotateR(parent);

}

else if (parent->_bf == 2 && parent->_right->_bf == -1)//右左双旋

{

RotateRL(parent);

}

else if (parent->_bf == -2 && parent->_left->_bf == 1)//左右双旋

{

RotateLR(parent);

}

}

return true;

}

Node* Find(const T& data)

{

Node* cur = _root;

while (cur)

{

if (cur->_data < data)

{

cur = cur->_right;

}

else if (cur->_data > data)

{

cur = cur->_left;

}

else

{

return cur;

}

}

return nullptr;

}

void InOrder()

{

_InOrder(_root);

cout << endl;

}

bool Empty()

{

return _root == nullptr;

}

size_t Size()

{

return _Size(_root);

}

size_t Height()

{

return _Height(_root);

}

bool IsAVLTree()

{

bool ret = true;

_IsAVLTree(_root, ret);

return ret;

}

private:

int _IsAVLTree(const Node* root,bool& ret)

{

if (root == nullptr)

return 0;

if (ret == false)

return 0;

int left = _IsAVLTree(root->_left,ret);

if (ret == false)

return 0;

int right = _IsAVLTree(root->_right,ret);

if (root->_bf!= right - left)

{

cout << "平衡因子异常" << endl;

ret = false;

return 0;

}

if (abs(right - left) >= 2)

{

cout << "左右子树高度差异常" << endl;

ret = false;

}

return left > right ? left + 1 : right + 1;

}

size_t _Height(const Node* root)

{

if (root == nullptr)

return 0;

int left = _Height(root->_left);

int right = _Height(root->_right);

return left > right ? left + 1 : right + 1;

}

// 左单旋

void RotateL(Node* parent)

{

//记录一下PR和PRL

Node* PR = parent->_right;

Node* PRL = PR->_left;

//把PRL链接在parent的右边

parent->_right = PRL;

//因为PRL可能为空，为了防止空指针访问，必须判断一下

if (PRL != nullptr)

{

//PRL不为空，就把它的父亲节点变成parent

PRL->_parent = parent;

}

//把parent链接在PR的左边

PR->_left = parent;

//更改PR的父亲节点

PR->_parent = parent->_parent;

//只有AVL树的根节点的父亲节点为空

//所以parent是根节点

if (parent->_parent == nullptr)

{

//PR变成了这颗子树的根，替代了原来parent的位置

//所以得把AVL树的根节点更新一下

_root = PR;

}

else//如果parent不是根节点

{

//PR还是要带替parent的位置

//所以parent在父亲的左，PR就在左

//parent在父亲的右，PR就在右

if (parent == parent->_parent->_left)

parent->_parent->_left = PR;

else

parent->_parent->_right = PR;

}

//更新一下parent的父亲节点

parent->_parent = PR;

//更新平衡因子

//只有parent和PR的平衡因子改变了

PR->_bf = 0;

parent->_bf = 0;

}

// 右单旋

void RotateR(Node* parent)

{

//记录一下PL和PLR

Node* PL = parent->_left;

Node* PLR = PL->_right;

//把PLR链接在parent的右边

parent->_left = PLR;

//因为PLR可能为空，为了防止空指针访问，必须判断一下

if (PLR != nullptr)

{

//不为空，就把它的父亲节点变成parent

PLR->_parent = parent;

}

//把parent链接在PL的左边

PL->_right = parent;

//更新PL的父亲节点

PL->_parent = parent->_parent;

//只有AVL树的根节点的父亲节点为空

//所以parent是根节点

if (parent->_parent == nullptr)

{

//PL变成了这颗子树的根，替代了原来parent的位置

//所以得把AVL树的根节点更新一下

_root = PL;

}

else//如果parent不是根节点

{

//PL还是要带替parent的位置

//所以parent在父亲的左，PL就在左

//parent在父亲的右，PL就在右

if (parent == parent->_parent->_left)

parent->_parent->_left = PL;

else

parent->_parent->_right = PL;

}

//更新一下parent的父亲节点

parent->_parent = PL;

//更新平衡因子

//只有parent和PL的平衡因子改变了

parent->_bf = 0;

PL->_bf = 0;

}

// 右左双旋

void RotateRL(Node* parent)

{

Node* PR = parent->_right;

Node* PRL = PR->_left;

int bf = PRL->_bf;

RotateR(parent->_right);

RotateL(parent);

//更新平衡因子

if (bf == 0)

{

parent->_bf = 0;

PR->_bf = 0;

PRL->_bf = 0;

}

else if (bf == 1)

{

parent->_bf = -1;

PR->_bf = 0;

PRL->_bf= 0;

}

else if (bf == -1)

{

parent->_bf = 0;

PR->_bf = 1;

PRL->_bf = 0;

}

}

// 左右双旋

void RotateLR(Node* parent)

{

//保存旋转之前的PL和PLR

//方便之后直接更新平衡因子

Node* PL = parent->_left;

Node* PLR = PL->_right;

//插在子树b上时，PRL的平衡因子为-1

//插在子树c上时，PRL的平衡因子为1

//所以可以通过这个，来判断新节点插在哪里了

//旋转过程中PRL的平衡因子可能会变，所以要提前保存

int bf = PLR->_bf;

//先对PL左旋

RotateL(parent->_left);

//再对parent右旋

RotateR(parent);

//根据情况，更新平衡因子

if (bf == 0)//即h==0的情况

{

parent->_bf = 0;

PL->_bf = 0;

PLR->_bf = 0;

}

//插在子树c上时，PRL的平衡因子为1

else if (bf == 1)

{

parent->_bf = 0;

PL->_bf = -1;

PLR->_bf = 0;

}

//插在子树b上时，PRL的平衡因子为-1

else if (bf == -1)

{

parent->_bf = 1;

PL->_bf = 0;

PLR->_bf = 0;

}

}

//因为无法直接获取到父亲节点的地址

//所以需要传参传进来

Node* Copy(Node* root, Node* parent)

{

//空节点不需要拷贝，直接返回nullptr

if (root == nullptr)

return nullptr;

//从堆区申请空间

Node* newnode = new Node(root->_data);

//连接上传入的父亲节点

newnode->_parent = parent;

newnode->_bf = root->_bf;

//递归拷贝左右子树

newnode->_left = Copy(root->_left,newnode);

newnode->_right = Copy(root->_right,newnode);

return newnode;

}

void Destroy(Node* root)

{

if (root == nullptr)

return;

Destroy(root->_left);

Destroy(root->_right);

delete root;

}

void _InOrder(Node* root)

{

if (root == nullptr)

return;

_InOrder(root->_left);//递归遍历左子树

cout << root->_data <<" ";//打印信息（遍历根）

_InOrder(root->_right);//递归遍历右子树

}

size_t _Size(Node* root)

{

if (root == nullptr)

return 0;

int left = _Size(root->_left);

int right = _Size(root->_right);

return left + right + 1;

}

};