AVL树的C++实现

enterdawn

共 5540字,需浏览 12分钟

 ·

2022-07-25 09:58

首先,AVL 树是二叉查找树,即任意一个节点的左子结点小于当前结点,右子结点大于当前结点。
然后,AVL 树是平衡树,任意一个结点的左子树和右子树高度差的绝对值小于等于 1。

定义


template <typename T>

class AVLTreeNode {

public:

T key;

int height = 1; //树高

AVLTreeNode* l;

AVLTreeNode* r;

AVLTreeNode(T _key, AVLTreeNode* _l, AVLTreeNode* _r) : key(_key), l(_l), r(_r) {}



};



template <typename T>

class AVLTree {

public:

AVLTreeNode<T>* root;

AVLTree() { this->root = nullptr; }

~AVLTree();

int height(AVLTreeNode<T>* tree);

int height();

void insert(T key);

void remove(T key);

AVLTreeNode<T>* find(T key);

void print();



private:

AVLTreeNode<T>* LLRotation(AVLTreeNode<T>* k2);

AVLTreeNode<T>* LRRotation(AVLTreeNode<T>* k2);

AVLTreeNode<T>* RRRotation(AVLTreeNode<T>* k2);

AVLTreeNode<T>* RLRotation(AVLTreeNode<T>* k2);

AVLTreeNode<T>* insert(T key, AVLTreeNode<T>* root);

AVLTreeNode<T>* remove(AVLTreeNode<T>* del, AVLTreeNode<T>* root);

AVLTreeNode<T>* find(T key, AVLTreeNode<T>* root);

AVLTreeNode<T>* findmax(AVLTreeNode<T>* root);

AVLTreeNode<T>* findmin(AVLTreeNode<T>* root);

};

旋转

AVL 树的旋转有 4 种,LL,RR,LR,RL。

LL




如图所示,当左子树的左子树影响平衡的时候,我们需要进行 LL 旋转。
首先,我们把 k1 提起来 (就像提绳子一样),这时候 k1 是根结点。但是这时候会发现 k1 有三个子节点,不符合二叉树的定义。同时又因为 k2 刚好被转过去,没有左子结点。所以我们就把 k1 原先的右子树给 k2 当左子树。
因为 k2 之前是根节点,所以 k2>k1 的右子结点 > k1,如上操作之后,符合 AVL 树的定义。
每次旋转之后都重新计算树高。




template <typename T>

AVLTreeNode<T>* AVLTree<T>::LLRotation(AVLTreeNode<T>* k2) {

AVLTreeNode<T>* k1;

k1 = k2->l;

k2->l = k1->r;

k1->r = k2;

k2->height = max(height(k2->l), height(k2->r)) + 1;

k1->height = max(height(k1->l), k2->height) + 1;

return k1;

}

RR




理解 LL 之后,RR 就很好理解。
当右子树的右子树影响平衡之后,我们首先把 k2 提起来,现在 k1 缺少右子结点,我们就把 k2 之前的左子树给过去。
因为 k2>k2 的左子结点 > k1,操作之后符合 AVL 树的定义。




template <typename T>

AVLTreeNode<T>* AVLTree<T>::RRRotation(AVLTreeNode<T>* k1) {

AVLTreeNode<T>* k2;

k2 = k1->r;

k1->r = k2->l;

k2->l = k1;

k1->height = max(height(k1->l), height(k1->r)) + 1;

k2->height = max(height(k2->r), k1->height) + 1;

return k2;

}

LR




当左子树的右子树影响平衡的时候,我们对右子树进行一次 RR 旋转,之后就转化为 LL 旋转。




template <typename T>

AVLTreeNode<T>* AVLTree<T>::LRRotation(AVLTreeNode<T>* root) {

root->l = RRRotation(root->l);

return LLRotation(root);

}

RL

理解以上几个之后,RL 也就很好理解了,此处不赘述,请读者自行思考。


template <typename T>

AVLTreeNode<T>* AVLTree<T>::RLRotation(AVLTreeNode<T>* root) {

root->r = LLRotation(root->r);

return RRRotation(root);

}

插入

我们递归查找插入的位置,回溯的过程中发现不平衡就去进行旋转。


template <typename T>

AVLTreeNode<T>* AVLTree<T>::insert(T key, AVLTreeNode<T>* root) {

if (root == nullptr) {

root = new AVLTreeNode<T>(key, nullptr, nullptr);

}

else if (key < root->key) {//插入到左子树

root->l = insert(key, root->l);

if (height(root->l) - height(root->r) == 2) {

if (key < root->l->key) {

root = LLRotation(root);

}

else {

root = LRRotation(root);

}

}

}

else if (key > root->key) {//插入到右子树

root->r = insert(key, root->r);

if (height(root->r) - height(root->l) == 2) {

if (key > root->r->key) {

root = RRRotation(root);

}

else {

root = RLRotation(root);

}

}

}

root->height = max(height(root->l), height(root->r)) + 1;

return root;

}



template <typename T>

void AVLTree<T>::insert(T key) {

root = insert(key, root);

}

查找和删除


template <typename T>

AVLTreeNode<T>* AVLTree<T>::find(T key) {

return find(key, root);

}



template <typename T>

AVLTreeNode<T>* AVLTree<T>::find(T key, AVLTreeNode<T>* root) {

if (root == nullptr)

return root;

if (key > root->key) {

return find(key, root->r);

}

else if (key < root->key) {

return find(key, root->l);

}

else

return root;

}



template <typename T>

AVLTreeNode<T>* AVLTree<T>::findmax(AVLTreeNode<T>* root) {

if (root->r == nullptr)

return root;

return findmax(root->r);

}



template <typename T>

AVLTreeNode<T>* AVLTree<T>::findmin(AVLTreeNode<T>* root) {

if (root->l == nullptr)

return root;

return findmin(root->l);

}



template <typename T>

AVLTreeNode<T>* AVLTree<T>::remove(AVLTreeNode<T>* del, AVLTreeNode<T>* root) {

//没找到直接返回

if (root == nullptr || del == nullptr)

return root;

if (del->key < root->key) {//需要删除的结点在左子树中

root->l = remove(del, root->l);

if (height(root->r) - height(root->l) == 2) {

if (height(root->r->l) > height(root->r->r)) {

root = RLRotation(root);

}

else {

root = RRRotation(root);

}

}

}

else if (del->key > root->key) {//需要删除的结点在右子树中

root->r = remove(del, root->r);

if (height(root->l) - height(root->r) == 2) {

if (height(root->l->r) > height(root->l->l)) {

root = LRRotation(root);

}

else {

root = LLRotation(root);

}

}

}

else {

//左右子树都不为空,删除后,我们可以用左子树的最大结点或右子树的最小结点来替换这个结点

if (root->l != nullptr && root->r != nullptr) {

if (height(root->l) > height(root->r)) {

//用左子树的最大结点,好处是删除后还是平衡的,无需旋转

AVLTreeNode<T>* mx = findmax(root->l);

root->key = mx->key;

root->l = remove(mx, root->l);

}

else {

//用右子树的最大结点,好处同上

AVLTreeNode<T>* mn = findmin(root->r);

root->key = mn->key;

root->r = remove(mn, root->r);

}



}

else {

AVLTreeNode<T>* tmp = root;

root = (root->l == nullptr) ? root->r : root->l;

delete tmp;

}

}

return root;

}



template <typename T>

void AVLTree<T>::remove(T key) {

root = remove(find(key), root);

}

总结

至于析构,遍历等等的代码和此处不再给出,请参照正常的二叉树操作自行思考。
AVL 树的实现实际上不难,由于各种教材上冗长的介绍,使得我们有一种认为它难的错觉。


浏览 36
点赞
评论
收藏
分享

手机扫一扫分享

分享
举报
评论
图片
表情
推荐
点赞
评论
收藏
分享

手机扫一扫分享

分享
举报