前言：

前面讲到了平衡搜索树（BST），但是不能会出现极端情况，出现线性的结构，今天介绍自平衡二叉搜索树（AVL）

AVL树

AVL的介绍

<code>AVL树是一种自平衡二叉搜索树：它以苏联科学家Georgy Adelson-Velsky和Evgenii Landis的名字命名。

在AVL树中，任何节点的两个子树的高度最多相差1，这保证了树的平衡性，从而使得树的操作（如插入、删除和查找）具有良好的最坏情况性能，时间复杂度为O(log n)

AVL树的旋转操作是其自平衡机制的核心，包括左旋、右旋、左-右旋和右-左旋。这些旋转调整节点的位置，减少子树的高度差，恢复树的平衡。

AVL树特性

严格的平衡性：AVL树的每个节点的左右子树的高度差的绝对值不超过1，这保证了树的高度最小，从而使得操作（如插入、删除和查找）的时间复杂度保持在对数级别。旋转调整：当插入或删除操作导致节点的平衡因子超出允许范围时，AVL树会通过单旋转或双旋转来重新平衡树。高效的搜索、插入和删除操作：由于<code>AVL树的高度平衡，这些操作的时间复杂度通常为O(log n)，其中n是树中节点的数量。节点定义：AVL树的节点通常包含数据、指向左右子节点的指针、指向父节点的指针以及记录子树高度差的平衡因子。高度记录：在AVL树中，每个节点还会记录其子树的高度，这有助于快速计算平衡因子并在需要时进行调整。适用场景：AVL树适用于需要频繁进行数据插入、删除和查找操作的场景，尤其是在数据集合较大时，可以保持较高的效率。

AVL树的核心

AVL树是一种自平衡的二叉查找树，它通过旋转调整机制来维持树的平衡。当树在插入或删除操作后出现不平衡时，AVL树会执行以下四种旋转操作之一来恢复平衡：

单旋转：

左旋（LL型）：当插入或删除操作导致某个节点的左子树的高度比右子树高2时，需要执行左旋操作。左旋操作涉及到将这个节点的右子树提升为新的根节点，并将原根节点作为左子节点挂接到新根节点上。右旋（RR型）：与左旋相反，当某个节点的右子树的高度比左子树高2时，执行右旋操作，即将左子树提升为新的根节点。 双旋转：

左-右旋（LR型）：当插入或删除操作导致某个节点的左子树的右子树的高度比左子树的右子树高时，先对左子树执行左旋，然后对原节点执行右旋。右-左旋（RL型）：与左-右旋相反，当某个节点的右子树的左子树的高度比右子树的左子树高时，先对右子树执行右旋，然后对原节点执行左旋。

AVL插入实现

AVL树是基于BST结构，大主体就是BST问题的解决就是AVL的单旋和双旋以及需要旋转的条件。

AVL的存贮结构

在这里面利用KV结构进行存储数据左右节点，还有一个父亲节点为了保持平衡定义_bf（平衡因子：balance factor）

template<class K, class V>

struct AVLNode

{ -- -->

pair<K, V> _kv;

AVLNode<K, V>* _left;

AVLNode<K, V>* _right;

AVLNode<K, V>* _parent;

int _bf;

AVLNode(const pair<K, V>& kv)

:_kv(kv)

, _left(nullptr)

, _right(nullptr)

, _parent(nullptr)

, _bf(0)

{ }

};

template<class K, class V>

class AVL

{

typedef AVLNode<K, V> Node;

private：

Node* _root;

}；

AVL的插入

如果根节点是nullptr时，进行特殊的判断，直接进行节点的创建查找插入的位置，大于在右边，小于在左边进行平衡因子的更新，左边插入，父亲节点-1，右边插入，父亲节点+1（可以反向操作）在节点更新的时候就要进行判断，只有发大于左右节点不平衡的时候需要旋转

左旋转 、右旋转、左右旋转、右左旋转（下面会详细介绍）

bool insert(const pair<K, V>& kv)

{

//step 1

if (_root == nullptr)

{

_root = new Node(kv);

return true;

}

Node* parent = nullptr;

Node* cur = _root;

//step 2

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;

}

else

{

//key 存在

return false;

}

}

cur = new Node(kv);

if (kv.first > parent->_kv.first)

{

parent->_right = cur;

}

else

{

parent->_left = cur;

}

cur->_parent = parent;

//step 3

//更新平衡因子

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 = parent;

parent = parent->_parent;

}

else if (parent->_bf == 2 || parent->_bf == -2)

{

if (cur->_bf == 1 && parent->_bf == 2)

{

RotateL(parent);

}

else if (cur->_bf == -1 && parent->_bf == -2)

{

RotateR(parent);

}

else if (cur->_bf == -1 && parent->_bf == 2)

{

RotateRL(parent);

}

else if (cur->_bf == 1 && parent->_bf == -2)

{

RotateLR(parent);

}

break;

}

else

{

assert(false);

}

}

AVL左旋

AVL树左旋的条件是：

当前节点的平衡因子（右子树的高度减去左子树的高度）为2，这意味着当前节点的左子树的高度至少比右子树高2。当前节点的右子树必须是一个有效的AVL子树，即它的两个子树的高度差不超过1。当前节点的左子树的右子节点（即当前节点的孙子节点）不为空

b节点摘下，放在30这个节点的右边将30这个整体放在60的左边更改父亲节点的关系，同时要注意的是B子树不为空，如果为空，就不要更新父亲节点。

<code>void RotateL(Node* parent)

{ -- -->

Node* cur = parent->_right;

Node* curleft = cur->_left;

parent->_right = curleft;

if (curleft)

{

curleft->_parent = parent;

}

cur->_left = parent;

Node* ppnode = parent->_parent;

parent->_parent = cur;

if (ppnode == nullptr)

{

_root = cur;

cur->_parent = nullptr;

}

else

{

if (ppnode->_left == parent)

{

ppnode->_left = cur;

}

else

{

ppnode->_right = cur;

}

cur->_parent = ppnode;

}

parent->_bf = cur->_bf = 0;

}

AVL右旋

AVL树进行右旋操作的条件：

当一个节点的平衡因子（BF）为-2时，表示该节点的左子树的高度至少比右子树高2，这违反了AVL树的平衡性要求。同时，该节点的左子节点的平衡因子必须为-1，这意味着左子节点的右子树存在，且其高度至少为1。

右旋的操作和左旋的操作成镜像

void RotateR(Node* parent)

{

Node* cur = parent->_left;

Node* curright = cur->_right;

parent->_left = curright;

if (curright)

{

curright->_parent = parent;

}

cur->_right = parent;

Node* ppnode = parent->_parent;

parent->_parent = cur;

if (ppnode == nullptr)

{

_root = cur;

cur->_parent = nullptr;

}

else

{

if (ppnode->_left == parent)

{

ppnode->_left = cur;

}

else

{

ppnode->_right = cur;

}

cur->_parent = ppnode;

}

cur->_bf = parent->_bf = 0;

}

AVL左-右旋

首先，找到需要旋转的节点，该节点的左子树的左子树高度大于右子树高度，导致平衡因子绝对值为2。对该节点的左子树执行左旋操作，这会使得原节点成为左子树新的右子节点，并且原节点的左子树的右子节点成为新的左子树根节点。接着，对原节点执行右旋操作，这会使得原节点成为整个子树的新根节点，并且原节点的左子节点（即之前左子树的右子节点）成为新根节点的左子节点。旋转后，更新所有相关节点的父节点指针，并重新计算平衡因子，确保树重新平衡。

<code>void RotateLR(Node* parent)

{ -- -->

Node* cur = parent->_left;

Node* curright = cur->_right;

int bf = curright->_bf;

RotateL(parent->_left);

RotateR(parent);

if (bf == 0)

{

curright->_bf = 0;

parent->_bf = 0;

cur->_bf = 0;

}

else if (bf == 1)

{

parent->_bf = 0;

cur->_bf = -1;

curright->_bf = 0;

}

else if (bf == -1)

{

parent->_bf = 1;

cur->_bf = 0;

curright->_bf = 0;

}

else

{

assert(false);

}

}

AVL右-左旋

首先对该节点的左子节点进行右旋操作，这会使得原本的左子节点成为新的根节点，而原来的右子节点成为左子节点的右孩子。接着对原来的节点（现在是右子节点的左孩子）进行左旋操作，这会使得原本的右子节点成为新的根节点，原来的节点成为右子节点的左孩子。注意更新三者的关系

<code>void RotateRL(Node* parent)

{ -- -->

Node* cur = parent->_right;

Node* curleft = cur->_left;

int bf = curleft->_bf;

RotateR(parent->_right);

RotateL(parent);

//解偶

if (bf == 0)

{

parent->_bf = 0;

cur->_bf = 0;

curleft->_bf = 0;

}

else if (bf == -1)

{

parent->_bf = 0;

cur->_bf = 1;

curleft->_bf = 0;

}

else if (bf == 1)

{

cur->_bf = 0;

parent->_bf = -1;

curleft->_bf = 0;

}

else

{

assert(false);

}

}

AVL树的检查

根据AVL的特性，左右子树之间的相差的值小于2.这就需要进行根节点的高度的计算。

//计算高度

int Height(Node* root)

{

if (root == nullptr)

{

return 0;

}

int leftHeight = Height(root->_left);

int rightHeight = Height(root->_right);

return max(leftHeight, rightHeight) + 1;

}

//判断平衡

bool is_balance(Node* root)

{

if (root == nullptr)

return true;

int leftHeight = Height(root->_left);

int rightHeight = Height(root->_right);

if (rightHeight - leftHeight != root->_bf)

{

cout << "balance id abnormal" << endl;

return false;

}

return abs(leftHeight - rightHeight) < 2 && is_balance(root->_left) && is_balance(root->_right);

}

源码

#pragma once

#include<vector>

#include<iostream>

#include<utility>

#include<assert.h>

using namespace std;

namespace AVL

{

template<class K, class V>

struct AVLNode

{

pair<K, V> _kv;

AVLNode<K, V>* _left;

AVLNode<K, V>* _right;

AVLNode<K, V>* _parent;

int _bf;

AVLNode(const pair<K, V>& kv)

:_kv(kv)

, _left(nullptr)

, _right(nullptr)

, _parent(nullptr)

, _bf(0)

{ }

};

template<class K, class V>

class AVL

{

typedef AVLNode<K, V> Node;

public:

AVL()

:_root(nullptr)

{ }

bool insert(const pair<K, V>& kv)

{

if (_root == nullptr)

{

_root = new Node(kv);

return true;

}

Node* parent = nullptr;

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;

}

else

{

//key 存在

return false;

}

}

cur = new Node(kv);

if (kv.first > parent->_kv.first)

{

parent->_right = cur;

}

else

{

parent->_left = 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 = parent;

parent = parent->_parent;

}

else if (parent->_bf == 2 || parent->_bf == -2)

{

if (cur->_bf == 1 && parent->_bf == 2)

{

RotateL(parent);

}

else if (cur->_bf == -1 && parent->_bf == -2)

{

RotateR(parent);

}

else if (cur->_bf == -1 && parent->_bf == 2)

{

RotateRL(parent);

}

else if (cur->_bf == 1 && parent->_bf == -2)

{

RotateLR(parent);

}

break;

}

else

{

assert(false);

}

}

return true;

}

int Height(Node* root)

{

if (root == nullptr)

{

return 0;

}

int leftHeight = Height(root->_left);

int rightHeight = Height(root->_right);

return max(leftHeight, rightHeight) + 1;

}

bool is_balance()

{

return is_balance(_root);

}

bool is_balance(Node* root)

{

if (root == nullptr)

return true;

int leftHeight = Height(root->_left);

int rightHeight = Height(root->_right);

if (rightHeight - leftHeight != root->_bf)

{

cout << "balance id abnormal" << endl;

return false;

}

return abs(leftHeight - rightHeight) < 2 && is_balance(root->_left) && is_balance(root->_right);

}

void RotateLR(Node* parent)

{

Node* cur = parent->_left;

Node* curright = cur->_right;

int bf = curright->_bf;

RotateL(parent->_left);

RotateR(parent);

if (bf == 0)

{

curright->_bf = 0;

parent->_bf = 0;

cur->_bf = 0;

}

else if (bf == 1)

{

parent->_bf = 0;

cur->_bf = -1;

curright->_bf = 0;

}

else if (bf == -1)

{

parent->_bf = 1;

cur->_bf = 0;

curright->_bf = 0;

}

else

{

assert(false);

}

}

void RotateRL(Node* parent)

{

Node* cur = parent->_right;

Node* curleft = cur->_left;

int bf = curleft->_bf;

RotateR(parent->_right);

RotateL(parent);

//解偶

if (bf == 0)

{

parent->_bf = 0;

cur->_bf = 0;

curleft->_bf = 0;

}

else if (bf == -1)

{

parent->_bf = 0;

cur->_bf = 1;

curleft->_bf = 0;

}

else if (bf == 1)

{

cur->_bf = 0;

parent->_bf = -1;

curleft->_bf = 0;

}

else

{

assert(false);

}

}

void RotateR(Node* parent)

{

Node* cur = parent->_left;

Node* curright = cur->_right;

parent->_left = curright;

if (curright)

{

curright->_parent = parent;

}

cur->_right = parent;

Node* ppnode = parent->_parent;

parent->_parent = cur;

if (ppnode == nullptr)

{

_root = cur;

cur->_parent = nullptr;

}

else

{

if (ppnode->_left == parent)

{

ppnode->_left = cur;

}

else

{

ppnode->_right = cur;

}

cur->_parent = ppnode;

}

cur->_bf = parent->_bf = 0;

}

void RotateL(Node* parent)

{

Node* cur = parent->_right;

Node* curleft = cur->_left;

parent->_right = curleft;

if (curleft)

{

curleft->_parent = parent;

}

cur->_left = parent;

Node* ppnode = parent->_parent;

parent->_parent = cur;

if (ppnode == nullptr)

{

_root = cur;

cur->_parent = nullptr;

}

else

{

if (ppnode->_left == parent)

{

ppnode->_left = cur;

}

else

{

ppnode->_right = cur;

}

cur->_parent = ppnode;

}

parent->_bf = cur->_bf = 0;

}

private:

Node* _root;

};

}

cur;

}

cur->_parent = ppnode;

}

cur->_bf = parent->_bf = 0;

}

void RotateL(Node* parent)

{

Node* cur = parent->_right;

Node* curleft = cur->_left;

parent->_right = curleft;

if (curleft)

{

curleft->_parent = parent;

}

cur->_left = parent;

Node* ppnode = parent->_parent;

parent->_parent = cur;

if (ppnode == nullptr)

{

_root = cur;

cur->_parent = nullptr;

}

else

{

if (ppnode->_left == parent)

{

ppnode->_left = cur;

}

else

{

ppnode->_right = cur;

}

cur->_parent = ppnode;

}

parent->_bf = cur->_bf = 0;

}

private:

Node* _root;

};

}