AVL树的模拟实现(插入，验证)

目录

前言

AVL树的概念

AVL树的旋转

旋转

左旋

右旋

左右旋

右左旋

AVL的insert的实现

AVL的验证

完整代码

总结

---

前言

本文会先将AVL树的旋转进行讲解， 然后再对代码进行实现和展示。 

AVL树的概念

首先 AVL树 是一种平衡树， 平衡树是在二叉搜索树的基础上进行平衡 ， AVL树是一种严格平衡（即 左右子树的高度差 不超过1）。 既然AVL树是在二叉搜索树的基础进行平衡的，因此AVL树也具备二叉搜索树的基本功能。

AVL树的旋转

我们用一个 平衡因子 _bf 对AVL树进行维护。平衡因子_bf 存储 左右子树的高度差。 此文以 _bf = 左子树高度 - 右子树高度    为基准。

旋转

什么时候进行旋转？ 当插入数据时， 可能进行旋转。 我们记 dest 为 要插入节点的位置， parent为dest节点的父节点。 而AVL树插入数据前具体有三种情况，如下图.

显然， 当在图【2】插入数据时，是必定不会旋转的。 而在图【1】的 3 ，4 位置， 以及图【3】的1，2位置插入数据时，也是必定不会旋转的

左旋

当在图【3】的 4 位置 插入会进左旋。 

左旋的流程：

代码实现

void RotateL(Node* parent)
{Node* pparent = parent->_parent;Node* Rchild = parent->_right;Node* RLchild = Rchild->_left;if(RLchild != nullptr)RLchild->_parent = parent;parent->_right = RLchild;Rchild->_parent = pparent;if (pparent != nullptr){if (parent == pparent->_left) pparent->_left = Rchild;else pparent->_right = Rchild;}else{_root = Rchild;}Rchild->_left = parent;parent->_parent = Rchild;Rchild->_bf = parent->_bf = 0;}

右旋

在图【1】的1位置插入 会进行右旋

右旋的流程:

代码实现：

void RotateR(Node* parent)
{Node* pparent = parent->_parent;Node* Lchild = parent->_left;Node* LRchild = Lchild->_right;if(LRchild != nullptr) LRchild->_parent = parent;parent->_left = LRchild;Lchild->_parent = pparent;if (pparent != nullptr){if (parent == pparent->_left) pparent->_left = Lchild;else pparent->_right = Lchild;}else{_root = Lchild;}parent->_parent = Lchild;Lchild->_right = parent;parent->_bf = Lchild->_bf = 0;
}

左右旋

在图【1】的2位置插入，需要左右旋。

将图【1】的2位置进行展开，如下图。

左右旋的流程

void RotateLR(Node* parent)
{Node* Lchild = parent->_left;Node* LRchild = Lchild->_right;RotateL(Lchild);RotateR(parent);if (LRchild->_bf == -1){parent->_bf = 1;Lchild->_bf = LRchild->_bf = 0;}else{Lchild->_bf = -1;LRchild->_bf = parent->_bf = 0;}
}

右左旋

在图【3】的3位置进行插入，进行右左旋

对图【3】的3位置进行展开

右左旋转流程：

代码实现：

	void RotateRL(Node* parent){Node* Rchild = parent->_right;Node* RLchild = Rchild->_left;RotateR(Rchild);RotateL(parent);if (RLchild->_bf == -1){RLchild->_bf = parent->_bf = 0;Rchild->_bf = 1;}else{parent->_bf = -1;RLchild = Rchild = 0;}}

AVL的insert的实现

插入成功返回true，插入失败返回false

bool insert(const T& x)
{if (_root == nullptr){_root = new Node(x);return true;}Node* node = _root;Node* parent = nullptr;while (node){if (x < node->_val){parent = node;node = node->_left;}else if (x > node->_val){parent = node;node = node->_right;}else{return false;}}Node* child = new Node(x);if (x < parent->_val){parent->_left = child;child->_parent = parent;parent->_bf--;}else{parent->_right = child;child->_parent = parent;parent->_bf++;}while (parent){if (parent->_bf == 0){break;}else if (parent->_bf == 1 || parent->_bf == -1){child = parent;parent = child->_parent;if (parent != nullptr){if (child == parent->_left) parent->_bf--;else parent->_bf++;}}else if (parent->_bf == 2 && child->_bf == 1){//左单旋RotateL(parent);}else if (parent->_bf == -2 && child->_bf == -1){//右单旋RotateR(parent);}else if (parent->_bf == 2 && child->_bf == -1){//右左双旋RotateRL(parent);}else if (parent->_bf == -2 && child->_bf == 1){//左右双旋转RotateLR(parent);}}return true;}

AVL的验证

	void IsAVLTree(){if (IsAVLTree(_root)) cout << "是AVL树" << endl;else cout << "不是AVL树" << endl;}
private:int GetHeight(Node* root){if (root == nullptr) return 0;int L = GetHeight(root->_left);int R = GetHeight(root->_right);return L > R ? L + 1 : R + 1;}bool IsAVLTree(Node* root){if (root == nullptr) return true;int L_Height = GetHeight(root->_left);int R_Height = GetHeight(root->_right);if (abs(L_Height - R_Height) > 1) return false;return IsAVLTree(root->_left) && IsAVLTree(root->_right);}

完整代码

template<class T>
struct Node
{T _val;Node<T>* _left;Node<T>* _right;Node<T>* _parent;int _bf = 0;Node(const T& x = T()): _val(x), _left(nullptr),_right(nullptr),_parent(nullptr){}
};template<class T>
class AVLTree
{typedef Node<T> Node;
private:Node* _root = nullptr;
public:bool insert(const T& x){if (_root == nullptr){_root = new Node(x);return true;}Node* node = _root;Node* parent = nullptr;while (node){if (x < node->_val){parent = node;node = node->_left;}else if (x > node->_val){parent = node;node = node->_right;}else{return false;}}Node* child = new Node(x);if (x < parent->_val){parent->_left = child;child->_parent = parent;parent->_bf--;}else{parent->_right = child;child->_parent = parent;parent->_bf++;}while (parent){if (parent->_bf == 0){break;}else if (parent->_bf == 1 || parent->_bf == -1){child = parent;parent = child->_parent;if (parent != nullptr){if (child == parent->_left) parent->_bf--;else parent->_bf++;}}else if (parent->_bf == 2 && child->_bf == 1){//左单旋RotateL(parent);}else if (parent->_bf == -2 && child->_bf == -1){//右单旋RotateR(parent);}else if (parent->_bf == 2 && child->_bf == -1){//右左双旋RotateRL(parent);}else if (parent->_bf == -2 && child->_bf == 1){//左右双旋转RotateLR(parent);}}return true;}void Order(){Order(_root);cout << endl;}void IsAVLTree(){if (IsAVLTree(_root)) cout << "是AVL树" << endl;else cout << "不是AVL树" << endl;}
private:int GetHeight(Node* root){if (root == nullptr) return 0;int L = GetHeight(root->_left);int R = GetHeight(root->_right);return L > R ? L + 1 : R + 1;}bool IsAVLTree(Node* root){if (root == nullptr) return true;int L_Height = GetHeight(root->_left);int R_Height = GetHeight(root->_right);if (abs(L_Height - R_Height) > 1) return false;return IsAVLTree(root->_left) && IsAVLTree(root->_right);}void Order(Node* root){if (root == nullptr) return;Order(root->_left);cout << root->_val << ' ';Order(root->_right);}void RotateL(Node* parent){Node* pparent = parent->_parent;Node* Rchild = parent->_right;Node* RLchild = Rchild->_left;if(RLchild != nullptr)RLchild->_parent = parent;parent->_right = RLchild;Rchild->_parent = pparent;if (pparent != nullptr){if (parent == pparent->_left) pparent->_left = Rchild;else pparent->_right = Rchild;}else{_root = Rchild;}Rchild->_left = parent;parent->_parent = Rchild;Rchild->_bf = parent->_bf = 0;}void RotateR(Node* parent){Node* pparent = parent->_parent;Node* Lchild = parent->_left;Node* LRchild = Lchild->_right;if(LRchild != nullptr) LRchild->_parent = parent;parent->_left = LRchild;Lchild->_parent = pparent;if (pparent != nullptr){if (parent == pparent->_left) pparent->_left = Lchild;else pparent->_right = Lchild;}else{_root = Lchild;}parent->_parent = Lchild;Lchild->_right = parent;parent->_bf = Lchild->_bf = 0;}void RotateRL(Node* parent){Node* Rchild = parent->_right;Node* RLchild = Rchild->_left;RotateR(Rchild);RotateL(parent);if (RLchild->_bf == -1){RLchild->_bf = parent->_bf = 0;Rchild->_bf = 1;}else{parent->_bf = -1;RLchild = Rchild = 0;}}void RotateLR(Node* parent){Node* Lchild = parent->_left;Node* LRchild = Lchild->_right;RotateL(Lchild);RotateR(parent);if (LRchild->_bf == -1){parent->_bf = 1;Lchild->_bf = LRchild->_bf = 0;}else{Lchild->_bf = -1;LRchild->_bf = parent->_bf = 0;}}
};

总结

实际上AVL树的实现的难点在于 AVL树旋转，搞明白旋转，剩下的就明了了