AI 助理
备案控制台
开发者社区 开发与运维 文章 正文

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

2021-12-01 143
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
本文涉及的产品
云解析 DNS，旗舰版 1个月
全局流量管理 GTM，标准版 1个月
公共DNS（含HTTPDNS解析），每月1000万次HTTP解析
简介： 【愚公系列】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;
}


文章标签：
云解析DNS
C++
C#
算法
关键词：
C#解析
算法解析
算法云解析DNS
数据结构树
数据结构云解析DNS
愚公搬代码
目录
相关文章
长梦
|
2天前
|
编译器 C# 开发者
C# 9.0 新特性解析
C# 9.0 是微软在2020年11月随.NET 5.0发布的重大更新，带来了一系列新特性和改进，如记录类型、初始化器增强、顶级语句、模式匹配增强、目标类型的新表达式、属性模式和空值处理操作符等，旨在提升开发效率和代码可读性。本文将详细介绍这些新特性，并提供代码示例和常见问题解答。
长梦
13 7
C# 9.0 新特性解析
qhhf_地道酬勤
|
11天前
|
存储 消息中间件 NoSQL
Redis数据结构：List类型全面解析
Redis数据结构——List类型全面解析：存储多个有序的字符串，列表中每个字符串成为元素 Eelement，最多可以存储 2^32-1 个元素。可对列表两端插入（push）和弹出（pop）、获取指定范围的元素列表等，常见命令。 底层数据结构：3.2版本之前，底层采用**压缩链表ZipList**和**双向链表LinkedList**；3.2版本之后，底层数据结构为**快速链表QuickList** 列表是一种比较灵活的数据结构，可以充当栈、队列、阻塞队列，在实际开发中有很多应用场景。
qhhf_地道酬勤
45 5
qhhf_地道酬勤
|
10天前
|
存储 NoSQL 关系型数据库
Redis的ZSet底层数据结构，ZSet类型全面解析
Redis的ZSet底层数据结构，ZSet类型全面解析；应用场景、底层结构、常用命令；压缩列表ZipList、跳表SkipList；B+树与跳表对比，MySQL为什么使用B+树；ZSet为什么用跳表，而不是B+树、红黑树、二叉树
qhhf_地道酬勤
31 0
是店小二呀
|
1月前
|
搜索推荐 索引
【初阶数据结构】深度解析七大常见排序|掌握底层逻辑与原理（二）
【初阶数据结构】深度解析七大常见排序|掌握底层逻辑与原理
是店小二呀
26 4
是店小二呀
|
1月前
|
搜索推荐 C++
【初阶数据结构】深度解析七大常见排序|掌握底层逻辑与原理（一）
【初阶数据结构】深度解析七大常见排序|掌握底层逻辑与原理
是店小二呀
29 4
平凡程序猿~
|
1月前
|
存储 算法 搜索推荐
数据结构--堆的深度解析
数据结构--堆的深度解析
平凡程序猿~
77 0
是店小二呀
|
1月前
|
人工智能 搜索推荐 算法
【初阶数据结构】深度解析七大常见排序|掌握底层逻辑与原理（三）
【初阶数据结构】深度解析七大常见排序|掌握底层逻辑与原理
是店小二呀
23 0
ephemerals__
|
7天前
|
C语言
【数据结构】栈和队列（c语言实现）（附源码）
本文介绍了栈和队列两种数据结构。栈是一种只能在一端进行插入和删除操作的线性表，遵循“先进后出”原则；队列则在一端插入、另一端删除，遵循“先进先出”原则。文章详细讲解了栈和队列的结构定义、方法声明及实现，并提供了完整的代码示例。栈和队列在实际应用中非常广泛，如二叉树的层序遍历和快速排序的非递归实现等。
ephemerals__
67 9
html的七十二变
|
3天前
|
存储 JavaScript 前端开发
执行上下文和执行栈
执行上下文是JavaScript运行代码时的环境，每个执行上下文都有自己的变量对象、作用域链和this值。执行栈用于管理函数调用，每当调用一个函数，就会在栈中添加一个新的执行上下文。
html的七十二变
14 2
dufadayang
|
5天前
|
存储
系统调用处理程序在内核栈中保存了哪些上下文信息？
【10月更文挑战第29天】系统调用处理程序在内核栈中保存的这些上下文信息对于保证系统调用的正确执行和用户程序的正常恢复至关重要。通过准确地保存和恢复这些信息，操作系统能够实现用户模式和内核模式之间的无缝切换，为用户程序提供稳定、可靠的系统服务。
dufadayang
27 4

热门文章

最新文章

  • 1
    C# 基础知识系列- 14 IO篇 文件的操作
  • 2
    C#中的结构与类
  • 3
    C#并行编程-PLINQ:声明式数据并行
  • 4
    C# Json处理日期和Table
  • 5
    C#中cookie读写加密中文字符
  • 6
    一个简单的C#多线程间同步的例子
  • 7
    乐在其中设计模式(C#) - 解释器模式(Interpreter Pattern)
  • 8
    c# 模拟window 操作鼠标|winapi
  • 9
    C#学习笔记——抽象类和抽象方法
  • 10
    C# 数字格式化 ToString
  • 1
    Java中的数据结构与算法优化策略
    47
  • 2
    使用Java实现高效的数据结构与算法
    40
  • 3
    Java中的数据结构与算法实现
    35
  • 4
    C#数据结构与算法入门教程，值得收藏学习！
    68
  • 5
    Java数据结构与算法优化
    39
  • 6
    Java中的数据结构与算法优化策略
    38
  • 7
    数据结构与算法：栈与队列
    29
  • 8
    数据结构与算法：数组的操作
    29
  • 9
    Java数据结构与算法优化
    56
  • 10
    数据结构与算法 - 图
    27

    • 相关课程

    更多
  • 第八届大学生创新创业大赛阿里命题IoT赛题解析
  • 云计算工程师解析与实战-网络专家篇（体验版）
  • 深入解析Docker容器化技术
  • Java面试疑难点解析 - 面试技巧及语言基础
  • Java面试疑难点解析 - Java Web开发
  • Java面试疑难点解析 - 系统架构及项目设计

    • 相关电子书

    更多
  • 神龙云服务器产品及技术深度解析
  • 弹性创造价值：基于ECS的最佳性价比实践解析
  • 又快又稳：阿里云下一代虚拟交换机解析

    • 相关实验场景

    更多
  • 使用Swing算法实现商品推荐
  • 通过云拨测对指定服务器进行Ping/DNS监测
  • RSA密码算法设计与实现
  • 欧拉图的构造性证明与算法实现
  • 推荐系统入门之使用ALS算法实现打分预测

    • 推荐镜像

    更多
  • DNS
  • NTP
  • kali-security
    • 下一篇
    DataWorks售前咨询