【愚公系列】2021年11月 C#版 数据结构与算法解析(AVL树)-阿里云开发者社区

开发者社区> 愚公搬代码> 正文

【愚公系列】2021年11月 C#版 数据结构与算法解析(AVL树)

简介: 【愚公系列】2021年11月 C#版 数据结构与算法解析(AVL树)
+关注继续查看

AVL树定义:在计算机科学中,AVL树是最先发明的自平衡二叉查找树。在AVL树中任何节点的两个子树的高度最大差别为1,所以它也被称为高度平衡树。增加和删除可能需要通过一次或多次树旋转来重新平衡这个树。AVL树得名于它的发明者G. M. Adelson-Velsky和E. M. Landis,他们在1962年的论文《An algorithm for the organization of information》中发表了它。

平衡二叉树是带有平衡条件的二叉查找树,指的是空树或者任一结点左、右高度差的绝对值不超过1的二叉树.适合用于插入删除次数比较少,但查找多的情况。

比如:

image.png

实现的难点在于,二叉树的平衡旋转

分为四种旋转,RR、LL、LR、RL旋转

RR旋转

image.png

麻烦结点在发现者右子树的右边,所以叫RR插入,需要RR旋转

LL旋转

image.png

麻烦结点在发现者左子树的左边,所以叫LL插入,需要LL旋转

LR旋转

image.png

RL旋转

image.png

C#实现源码

public class Bit : IComparable<Bit>
{
    public int Value;

    public Bit(int value) => Value = value;

    public int CompareTo(Bit other) => Value - other.Value;
}
public class AvlTreeNote<TKey> where TKey : IComparable<TKey>
{
    public TKey Key;
    public int Height;
    public AvlTreeNote<TKey> LChild;
    public AvlTreeNote<TKey> RChild;

    public AvlTreeNote(TKey key, AvlTreeNote<TKey> lChild, AvlTreeNote<TKey> rChild)
    {
        Key = key;
        LChild = lChild;
        RChild = rChild;
    }
}
public class AvlTree<TKey> where TKey : IComparable<TKey>
{
    public AvlTreeNote<TKey> Root;          // 根节点

    private bool _isBalance;                // 标志是否平衡过二叉树

    /// <summary>
    /// 插入节点
    /// </summary>
    /// <param name="key"></param>
    /// <returns></returns>
    public AvlTreeNote<TKey> Insert(TKey key) => Root = Insert(key, Root);

    /// <summary>
    /// 插入到指定节点下
    /// </summary>
    /// <param name="key"></param>
    /// <param name="node"></param>
    /// <returns></returns>
    private AvlTreeNote<TKey> Insert(TKey key, AvlTreeNote<TKey> node)
    {
        if (node == null)
        {
            node = new AvlTreeNote<TKey>(key, null, null);
        }
        else
        {
            // 如果树里已经存在该节点,直接返回为null

            if (key.CompareTo(node.Key) == 0) return null;

            if (key.CompareTo(node.Key) < 0)
            {
                // 应该在左树进行搜索插入

                node.LChild = Insert(key, node.LChild);

                if (node.LChild == null) return node;

                switch (node.Height)
                {
                    case 1:
                        return LeftBalance(node);
                    case 0:
                        node.Height = _isBalance ? 0 : 1;
                        break;
                    case -1:
                        node.Height = 0;
                        break;
                }
            }
            else
            {
                // 应该在右树进行搜索插入

                node.RChild = Insert(key, node.RChild);

                if (node.RChild == null) return node;

                switch (node.Height)
                {
                    case 1:
                        node.Height = 0;
                        break;
                    case 0:
                        node.Height = _isBalance ? 0 : -1;
                        break;
                    case -1:
                        return RightBalance(node);
                }
            }
        }

        _isBalance = false;

        return node;
    }

    /// <summary>
    /// 左树平衡处理
    /// </summary>
    /// <param name="node"></param>
    private AvlTreeNote<TKey> LeftBalance(AvlTreeNote<TKey> node)
    {
        if (_isBalance) return node;

        var leftNode = node.LChild;

        switch (leftNode.Height)
        {
            case 1:

                node.Height = leftNode.Height = 0;

                node = R_Rotate(node);

                break;

            case -1:

                node.Height = leftNode.Height = 0;

                node.LChild = L_Rotate(leftNode);

                node = R_Rotate(node);

                break;
        }

        return node;
    }

    private AvlTreeNote<TKey> RightBalance(AvlTreeNote<TKey> node)
    {
        if (_isBalance) return node;

        var rightNode = node.RChild;

        switch (rightNode.Height)
        {
            case -1:

                node.Height = rightNode.Height = 0;

                node = L_Rotate(node);

                break;

            case 1:

                node.Height = rightNode.Height = 0;

                node.RChild = R_Rotate(rightNode);

                node = L_Rotate(node);

                break;
        }

        return node;
    }

    /// <summary>
    /// 右旋操作
    /// </summary>
    /// <param name="node"></param>
    private AvlTreeNote<TKey> R_Rotate(AvlTreeNote<TKey> node)
    {
        var temp = node.LChild;

        node.LChild = temp.RChild;

        temp.RChild = node;

        _isBalance = true;

        return temp;
    }

    /// <summary>
    /// 左旋操作
    /// </summary>
    /// <param name="node"></param>
    private AvlTreeNote<TKey> L_Rotate(AvlTreeNote<TKey> node)
    {
        var temp = node.RChild;

        node.RChild = temp.LChild;

        temp.LChild = node;

        _isBalance = true;

        return temp;
    }

    /// <summary>
    /// 查找二叉树
    /// </summary>
    /// <param name="key"></param>
    /// <returns></returns>
    public AvlTreeNote<TKey> Find(TKey key) => Find(key, Root);

    /// <summary>
    /// 查找二叉树
    /// </summary>
    /// <param name="key"></param>
    /// <param name="node"></param>
    /// <returns></returns>
    public AvlTreeNote<TKey> Find(TKey key, AvlTreeNote<TKey> node)
    {
        if (node == null) return null;

        if (key.CompareTo(node.Key) < 0)
        {
            node = Find(key, node.LChild);
        }
        else if (key.CompareTo(node.Key) > 0)
        {
            node = Find(key, node.RChild);
        }

        return node;
    }

    /// <summary>
    /// 用于删除该节点移动节点
    /// </summary>
    /// <param name="node"></param>
    /// <param name="findNode"></param>
    /// <returns></returns>
    private AvlTreeNote<TKey> Move(AvlTreeNote<TKey> node, AvlTreeNote<TKey> findNode)
    {
        AvlTreeNote<TKey> moveNode;

        if (findNode != null)
        {
            if (findNode.RChild != null)
            {
                moveNode = findNode.RChild;

                findNode.RChild = null;
            }
            else
            {
                findNode.LChild = null;

                moveNode = findNode;
            }

            if (node.LChild != moveNode) moveNode.LChild = node.LChild;

            if (node.RChild != moveNode) moveNode.RChild = node.RChild;
        }
        else
        {
            moveNode = null;
        }

        node.LChild = null;

        node.RChild = null;

        node.Key = default(TKey);

        node.Height = 0;

        return moveNode;
    }

    /// <summary>
    /// 删除节点
    /// </summary>
    /// <param name="key"></param>
    public void Remove(TKey key) => Root = Remove(key, Root);

    private AvlTreeNote<TKey> Remove(TKey key, AvlTreeNote<TKey> node)
    {
        if (node == null) return null;

        if (key.CompareTo(node.Key) < 0)
        {
            if (node.LChild == null) return node;

            node.LChild = Remove(key, node.LChild);

            switch (node.Height)
            {
                case 1:
                    node.Height = 0;
                    break;
                case 0:
                    node.Height = -1;
                    break;
                case -1:
                    // 要进行旋转
                    node.Height = 0;
                    return node.LChild == null ? RightBalance(node) : LeftBalance(node);
            }
        }
        else if (key.CompareTo(node.Key) > 0)
        {
            if (node.RChild == null) return node;

            node.RChild = Remove(key, node.RChild);

            switch (node.Height)
            {
                case 1:
                    // 要进行旋转
                    node.Height = 0;
                    return node.RChild == null ? LeftBalance(node) : RightBalance(node);
                    break;
                case 0:
                    node.Height = 1;
                    break;
                case -1:
                    node.Height = 0;
                    break;
            }
        }
        else if (key.CompareTo(node.Key) == 0)
        {
            var findNode = Remove(key, node.LChild);

            node = Move(node, findNode);
        }

        _isBalance = false;

        return node;
    }
}

C/C++实现

#include <stack>//栈
#include <queue>
#include <iostream>
#include <initializer_list>
using namespace std;
template <typename Comparable>
class AVLTree
{
private:
    static const int ALLOWED_IMBLANCE = 1;
    struct AVLNode
    {
        Comparable element;
        AVLNode * left;
        AVLNode * right;
        int height;

        AVLNode(const Comparable & theElement, AVLNode *lt, AVLNode *rt,int h = 0)
            :element(theElement), left(lt), right(rt),height(h) {}
        AVLNode(Comparable && theElement, AVLNode *lt, AVLNode *rt, int h = 0)
            :element(std::move(theElement)), left(lt), right(rt),height(h) {}
    };
    AVLNode * root;
    void Insert(const Comparable &x, AVLNode * & t);
    void Insert(Comparable && x, AVLNode *&t);
    void Insert(initializer_list<Comparable> &d, AVLNode *& t);
    void Remove(const Comparable &x, AVLNode *&t);
    AVLNode * findMin(AVLNode *t)const;
    AVLNode * findMax(AVLNode *t)const;
    bool contains(const Comparable &x, AVLNode *t) const;
    void makeEmpty(AVLNode * &t);
    void PrintTree(AVLNode *t) const;
    AVLNode* clone(AVLNode *t)const
    {
        if (t == nullptr)
            return nullptr;
        return new AVLNode(t->element, clone(t->left), clone(t->right));
    }
    void rotateWithLeftChild(AVLNode *& k2);
    void rotateWithRightChild(AVLNode *& k2);
    void doubleWithLeftChild(AVLNode *&k3);
    void doubleWithRightChild(AVLNode *&k3);
    void balance(AVLNode*& t);
public:
    AVLTree() :root(nullptr) {}
    AVLTree(const AVLTree & rhs) :root(nullptr) { root = clone(rhs.root); }
    AVLTree(AVLTree && rhs) :root(nullptr) {    root = rhs.root;rhs = nullptr;}
    ~AVLTree() { makeEmpty(); }
    const Comparable & findMin() const { return findMin(root)->element; }
    const Comparable & findMax() const { findMax(root)->element; }
    bool contains(const Comparable & x) const { return contains(x, root); }
    bool isEmpty() const { return root == nullptr; }
    int height(AVLNode *t) const { return t == nullptr ? -1 : t->height; }
    void PrintTree()const { PrintTree(root); }
    void makeEmpty() { makeEmpty(root); }
    void Insert(const Comparable &x) { Insert(x,root); }
    void Insert(Comparable && x) { Insert(x,root); }
    void Insert(initializer_list<Comparable>d) { Insert(d, root); }
    void Remove(const Comparable &x) { Remove(x, root); }
    AVLTree & operator=(const AVLTree & rhs)
    {
        if (this != &rhs)
        {
            makeEmpty();
            root = clone(rhs.root);
        }
        return *this;
    }
    AVLTree & operator=(AVLTree && rhs)
    {
        if (this != &rhs)
        {
            makeEmpty();
            root = rhs.root;
            rhs.root = nullptr;
        }
        return *this;
    }
    friend int Max(int a, int b);

};
int Max(int a, int b)
{
    return (a > b) ? a : b;
}
template<typename Comparable>
void AVLTree<Comparable>::Insert(const Comparable & x, AVLNode *& t)
{
    if (t == nullptr)
    {
        t = new AVLNode(x, nullptr, nullptr);
    }
    else if (x < t->element)
        Insert(x, t->left);
    else if (t->element < x)
        Insert(x, t->right);

    balance(t);

}

template<typename Comparable>
void AVLTree<Comparable>::Insert(Comparable && x, AVLNode *& t)
{

    if (t == nullptr)
    {
        t = new AVLNode(std::move(x), nullptr, nullptr);
    }
    else if (x < t->element)
        Insert(std::move(x), t->left);
    else if (t->element < x)
        Insert(std::move(x), t->right);
    balance(t);
}

template<typename Comparable>
void AVLTree<Comparable>::Insert(initializer_list<Comparable> &d, AVLNode *& t)
{
    for (auto p = d.begin(); p != d.end(); p++)
    {
        Insert(*p, t);
    }
}
template<typename Comparable>
void AVLTree<Comparable>::Remove(const Comparable & x, AVLNode *& t)
{
    if (t == nullptr) //没找到相应的项什么都不做
        return;
    if (x < t->element)
        Remove(x, t->left);
    else if (x > t->element)
        Remove(x, t->right);
    else if (t->left != nullptr && t->right != nullptr)//找到了 但是有两个儿子
    {//取右子树的最小元素替代 或者左子树的最大元素,好处是右子树的最小元素一定在右子树的最左边,左子树的最大元素一定在左子树的最右边
        t->element = findMin(t->right)->element;//在右子树中找到最小的元素填充删除结点
        Remove(t->element, t->right);//在删除节点的右子树中删除最小元素.
    }
    else //有一个儿子 或者没有
    {
        AVLNode * oldNode = t;
        t = (t->left != nullptr) ? t->left : t->right; //如果有儿子,就让儿子接上,如果没有那t就设置为nullptr
        delete oldNode;
    }
    balance(t);
}

template<typename Comparable>
typename AVLTree<Comparable>::AVLNode *
AVLTree<Comparable>::findMin(AVLNode * t) const
{
    //递归版本
    //if (t == nullptr)  
    //  return nullptr;
    //if (t->left == nullptr)
    //  return t;
    //return findMin(t->left);

    //非递归版本
    if (t != nullptr)
        while (t->left != nullptr)
            t = t->right;
    return t;

}

template<typename Comparable>
typename AVLTree<Comparable>::AVLNode *
AVLTree<Comparable>::findMax(AVLNode * t)const
{
    //递归版本
    /*if (t == nullptr)
        return;
    if (t->right == nullptr)
        return t;
    return findMax(t->right);*/
    if (t != nullptr)
        while (t->right != nullptr)
            t = t->right;
    return t;


}

template<typename Comparable>
bool AVLTree<Comparable>::contains(const Comparable & x, AVLNode * t) const
{
    //递归版本
    /*if (t == nullptr)
        return false;
    else if (x < t->element)
        return contains(x, t->left);
    else if (x > t->element)
        return contains(x, t->right);
    else
        retu true;*/

        //非递归版本
    while (t != nullptr)
    {
        if (x < t->element)
            t = t->left;
        else if (x > t->element)
            t = t->right;
        else
            return true;
    }
    return false;
}

template<typename Comparable>
void AVLTree<Comparable>::makeEmpty(AVLNode *& t)
{

    if (t != nullptr)
    {
        makeEmpty(t->left);
        makeEmpty(t->right);
        delete t;
    }
    t = nullptr;

}

template<typename Comparable>
void AVLTree<Comparable>::PrintTree(AVLNode * t) const
{
    //递归先序遍历
    if (t != nullptr)
    {
        std::cout << t->element << " "; //先序遍历
        PrintTree(t->left);
        PrintTree(t->right);
    }
    //非递归的先序遍历, 使用栈
    //AVLNode * temp = t;
    //stack<AVLNode*>s;
    //while (temp || !s.empty())
    //{
    //  while (temp) //一直向左将沿途结点压入栈
    //  {
    //      s.push(temp);
    //      temp = temp->left;
    //  }
    //  if (!s.empty())
    //  {
    //      temp = s.top();
    //      s.pop();
    //      std::cout << temp->element << " "; //先序遍历
    //      temp = temp->right;
    //  }
    //}
    //层序遍历,使用队列
    //AVLNode * temp;
    //queue<AVLNode*>q;
    //if (t == nullptr)
    //  return;
    //q.push(t);
    //while (!q.empty())
    //{
    //  temp = q.front();
    //  q.pop();
    //  std::cout << temp->element << " ";
    //  if (temp->left)
    //      q.push(temp->left);
    //  if (temp->right)
    //      q.push(temp->right);
    //}


}

template<typename Comparable>
void AVLTree<Comparable>::rotateWithLeftChild(AVLNode *& k2)//左旋
{
    AVLNode *k1 = k2->left;
    k2->left = k1->right;
    k1->right = k2;
    k2->height = Max(height(k2->left), height(k2->right)) + 1;
    k1->height = Max(height(k1->left), k2->height) + 1;
    k2 = k1;//把所有的设置都变为改变后的设置
}

template<typename Comparable>
void AVLTree<Comparable>::rotateWithRightChild(AVLNode *& k2)//右旋
{
    AVLNode *k1 = k2->right;
    k2->right = k1->left;
    k1->left = k2;
    k2->height = Max(height(k2->right), height(k2->left)) + 1;
    k1->height = Max(height(k1->right), k2->height) + 1;
    k2 = k1;

}

template<typename Comparable>
void AVLTree<Comparable>::doubleWithLeftChild(AVLNode *& k3)//左右旋转
{
    rotateWithRightChild(k3->left);
    rotateWithLeftChild(k3);
}

template<typename Comparable>
void AVLTree<Comparable>::doubleWithRightChild(AVLNode *& k3)//右左旋转
{
    rotateWithLeftChild(k3->right);
    rotateWithRightChild(k3);
}

template<typename Comparable>
void AVLTree<Comparable>::balance(AVLNode *& t)
{
    if (t == nullptr)
    {
        return;
    }
    if (height(t->left) - height(t->right) > ALLOWED_IMBLANCE)
        if (height(t->left->left) >= height(t->left->right))
            rotateWithLeftChild(t);
        else
            doubleWithLeftChild(t);
    else if(height(t->right) - height(t->left) > ALLOWED_IMBLANCE)
        if (height(t->right->right) >= height(t->right->left))
            rotateWithRightChild(t);
        else
            doubleWithRightChild(t);
    t->height = max(height(t->left), height(t->right)) + 1;
}


版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
阿里云服务器怎么设置密码?怎么停机?怎么重启服务器?
如果在创建实例时没有设置密码,或者密码丢失,您可以在控制台上重新设置实例的登录密码。本文仅描述如何在 ECS 管理控制台上修改实例登录密码。
9943 0
SSL/TLS算法流程解析
SSL/TLS 早已不是陌生的词汇,然而其原理及细则却不是太容易记住。本文将试图通过一些简单图示呈现其流程原理,希望读者有所收获。   一、相关版本 Version Source Description   Browser Support SSL v2.
1202 0
【愚公系列】2021年11月 C#版 数据结构与算法解析(分块查找)
【愚公系列】2021年11月 C#版 数据结构与算法解析(分块查找)
5 0
常用加密算法解析
今天介绍下工作当中常用的加密算法、分类、应用。 1、对称加密算法 所谓对称,就是采用这种加密方法的双方使用方式用同样的密钥进行加密和解密。密钥是控制加密及解密过程的指令。
1468 0
对称加解密算法解析
一、概述 cryptosystem密码学系统分为私钥系统及公钥系统。 私钥系统:指加解密双方事先做了私有信息约定,采用对称密钥算法; 公钥系统:指发送方用公开凭证对数据进行加密后传输,接收方使用私有凭证进行解密,采用非对称密钥算法; 对称加密分类 流加密(stream cipher),加密和解密双方使用相同伪随机加密数据流,一般都是逐位异或或者随机置换数据内容,常见的流加密算法如RC4。
966 0
【大创_社区划分】——PageRank算法的解析与Python实现
一、什么是pagerank PageRank的Page可是认为是网页,表示网页排名,也可以认为是Larry Page(google 产品经理),因为他是这个算法的发明者之一,还是google CEO(^_^)。
1102 0
【愚公系列】2021年11月 C#版 数据结构与算法解析(Trie树)
【愚公系列】2021年11月 C#版 数据结构与算法解析(Trie树)
10 0
阿里云服务器如何登录?阿里云服务器的三种登录方法
购买阿里云ECS云服务器后如何登录?场景不同,阿里云优惠总结大概有三种登录方式: 登录到ECS云服务器控制台 在ECS云服务器控制台用户可以更改密码、更换系.
13691 0
+关注
愚公搬代码
该博客包括:.NET、前端、IOS、Android、Linux、物联网、网络安全、python、大数据等相关使用及进阶知识。查看博客过程中,如有任何问题,皆可随时沟通。
150
文章
0
问答
文章排行榜
最热
最新
相关电子书
更多
《2021云上架构与运维峰会演讲合集》
立即下载
《零基础CSS入门教程》
立即下载
《零基础HTML入门教程》
立即下载