备案控制台
开发者社区 云原生 文章 正文

AVL树的实现（万字图文详解）

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


底层结构

map和set的使用 ---- multiset和multimap

我们已经比较了解map/multimap/set/multiset，在其文档介绍中发现，这几个容器有个共同点是：其底层都是按照二叉搜索树来实现的，但是二叉搜索树有其自身的缺陷，假如往树中插入的元素有序或者接近有序，二叉搜索树就会退化成单支树，时间复杂度会退化成O(N)，因此map、set等关联式容器的底层结构是对二叉树进行了平衡处理，即采用平衡树来实现。

1. AVL的概念

二叉搜索树虽可以缩短查找的效率，但如果数据有序或接近有序二叉搜索树将退化为单支树，查找元素相当于在顺序表中搜索元素，效率低下。因此，两位俄罗斯的数学家G.M.Adelson-Velskii和E.M.Landis在1962年发明了一种解决上述问题的方法：当向二叉搜索树中插入新结点后，如果能保证每个结点的左右子树高度之差的绝对值不超过1(需要对树中的结点进行调整)，即可降低树的高度，从而减少平均搜索长度。

一棵AVL树或者是空树，或者是具有以下性质的二叉搜索树：

  • 它的左右子树都是AVL树
  • 左右子树高度之差(简称平衡因子)的绝对值不超过1(-1/0/1)

    如果一棵二叉搜索树是高度平衡的，它就是AVL树。如果它有n个结点，其高度可保持在O ( l o g 2 n ) O(log_2 n)O(log2n)，搜索时间复杂度O(l o g 2 n log_2 nlog2n)。

2. AVL树节点的定义

template <class K, class V>
struct AVLTreeNode
{
  AVLTreeNode<K,V>* _left;//左孩子节点
  AVLTreeNode<K,V>* _right;//右孩子节点
  AVLTreeNode<K,V>* _parent;//父亲节点
  pair<K, V> _kv; //存储键值对的pair对象，其中K表示键的类型，V表示值的类型。
  int _bf;//该节点的平衡因子：高度差
  AVLTreeNode(const pair<K, V>& kv)
    :_left(nullptr)
    , _right(nullptr)
    , _parent(nullptr)
    ,_kv(kv)
    ,_bf(0)
  {}
};

结构体中包含以下成员变量：

  • _left：指向左孩子节点的指针。
  • _right：指向右孩子节点的指针。
  • _parent：指向父节点的指针。
  • _kv：存储键值对的pair对象，其中K表示键的类型，V表示值的类型。
  • _bf：该节点的平衡因子，用于衡量左右子树高度差。

结构体中还定义了一个构造函数AVLTreeNode(const pair<K, V>& kv)，用于初始化节点对象。构造函数会对成员变量进行初始化，其中：

  • _left、_right、_parent被初始化为nullptr，表示当前节点没有左孩子、右孩子和父节点。
  • _kv被初始化为传入的键值对对象kv。
  • _bf被初始化为0，表示当前节点的平衡因子为0。
  • 通过这个结构体，可以创建AVL树的节点对象，并且使用成员变量来访问和修改节点的属性。

3. AVL树的插入

AVL树就是在二叉搜索树的基础上引入了平衡因子，因此AVL树也可以看成是二叉搜索树。那么AVL树的插入过程可以分为两步：

  1. 按照二叉搜索树的方式插入新节点
  2. 调整节点的平衡因子

先创建一个AVLTree的类

注：本文定义的函数全部都在AVLTree类中

//class默认是private
template <class K,class V>
class AVLTree
{
typedef  AVLTreeNode<K, V> Node;
public:
  bool insert(const pair<K,V>& kv)
  {}
  //....
private:
  Node* _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->_left;
    }
    else if (kv.first > cur->_kv.first)
    {
      parent = cur;
      cur = cur->_right;
    }
    else
    {
      return false;
    }
  }
  cur = new Node(kv);
  if (kv.first < parent->_kv.first)
  {
    parent->_left = cur;
    cur->_parent = parent;
  }
  if (kv.first > parent->_kv.first)
  {
    parent->_right = cur;
    cur->_parent = parent;
  }
  ///
  AVL的开始
  ..........
  return true;
}

分析

如果影响祖先，怎么影响？分析如下：

现在可以把AVL的插入操作大概框架写一下了：

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->_left;
    }
    else if (kv.first > cur->_kv.first)
    {
      parent = cur;
      cur = cur->_right;
    }
    else
    {
      return false;
    }
  }
  cur = new Node(kv);
  if (kv.first < parent->_kv.first)
  {
    parent->_left = cur;
    cur->_parent = parent;
  }
  if (kv.first > parent->_kv.first)
  {
    parent->_right = cur;
    cur->_parent = parent;
  }
  ///
  //AVL的开始
  while (parent)
  {
    // 更新双亲的平衡因子
    if (cur == parent->_left)
    {
      parent->_bf--;
    } 
    else
    {
      parent->_bf++;
    }
    //说明更新前是-1或者1，并且更新后父节点左右平衡，不用继续往上更新了
    if (parent->_bf == 0)
    {
      break;
    }
    //说明更新前bf是0，必须往上进行更新
    else if (parent->_bf == 1 || parent->_bf == -1)
    {
      cur = parent;
      parent = parent->_parent;
    }
    //说明更新前是-1或者1，并且更新后的子树违反了AVL树的规则，需要进行调整
    else if(parent->_bf == 2 || parent->_bf == -2)
    {
      //调整处理
      //........
    }
  }
  return true;
}

情况1一和情况二都好说

重点在于情况三的调整，下面将重点介绍调整的思路：“旋转”

4. AVL树的旋转

如果在一棵原本是平衡的AVL树中插入一个新节点，可能造成不平衡，此时必须调整树的结构，使之平衡化。根据节点插入位置的不同，AVL树的旋转分为四种：

4.1 新节点插入较高右子树的右侧—右右：左单旋

思路：

  • 将父节点的右孩子保存为SubR，将SubR的左孩子保存为SubRL。
  • 旋转链接，将SubRL作为父节点的右孩子，将父节点作为SubR的左孩子。
  • 获取父节点的父节点，并根据情况将SubR连接到父节点的父节点的相应位置。
  • 更新旋转后节点的平衡因子为0。
//左单旋
//（1.父亲节点的右边等于右孩子的左边; 2.右孩子的左边等于父亲节点）
//【把右孩子的左边给给父亲节点的右边; 2.再把父亲节点给给右孩子的左边】
void RotateL(Node *parent)
{
  Node* SubR = parent->_right;// 将父节点的右孩子保存为SubR
  Node* SubRL = SubR->_left;// 将SubR的左孩子保存为SubRL
  //旋转链接
  parent->_right = SubRL;// 将SubRL作为父节点的右孩子
  SubR->_left = parent; // 将父节点作为SubR的左孩子
  Node* Parent_Parent = parent->_parent;// 获取父节点的父节点
  parent->_parent = SubR; // 将SubR作为父节点的父节点
  if (SubRL)
  {
  // 如果SubRL存在，则将其父节点指针指向父节点
    SubRL->_parent = parent;
  }
  //和父节点的父节点链接
  if (_root == parent)
  {
    _root = SubR;// 如果parent是根节点，将SubR设为新的根节点
    SubR->_parent = nullptr;// 新的根节点的父节点指针设为nullptr
  }
  else
  {
    if (Parent_Parent->_left == parent)
    {
    // 将SubR作为父节点的父节点的左孩子
      Parent_Parent->_left = SubR;
    }
    else
    {
    // 将SubR作为父节点的父节点的右孩子
      Parent_Parent->_right = SubR;
    }
    SubR->_parent = Parent_Parent;// 将SubR的父节点指针指向父节点的父节点
  }
  //更新平衡因子
  SubR->_bf = parent->_bf = 0;
}

4.2 新节点插入较高左子树的左侧—左左：右单旋

右单旋和左单旋完全类似：老铁们可以参考左单旋先写一遍再来看代码

思路：

  • 将父节点的左孩子保存为SubL，将SubL的右孩子保存为SubLR。
  • 旋转链接，将SubLR作为父节点的左孩子，将父节点作为SubL的右孩子。
  • 获取父节点的父节点，并根据情况将SubL连接到父节点的父节点的相应位置。
  • 更新旋转后节点的平衡因子为0。
//右单旋
void RotateR(Node* parent)
{
  Node* SubL = parent->_left;
  Node* SubLR = SubL->_right;
  //旋转链接
  //动一个节点就把他的父亲也变动
  parent->_left = SubLR;
  if (SubLR)//SubLR可能为空
  {
    SubLR->_parent = parent;
  }
  Node* Parent_Parent = parent->_parent;
  SubL->_right = parent;
  parent->_parent = SubL; 
  //和父节点的父节点链接
  if (_root == parent)
  {
    _root = SubL;
    SubL->_parent = nullptr;
  }
  else
  {
    if (Parent_Parent->_left == parent)
    {
      Parent_Parent->_left = SubL;
    }
    else
    {
      Parent_Parent->_right = SubL;
    }
    SubL->_parent = Parent_Parent;//链接
  }
  SubL->_bf = parent->_bf = 0;
  //更新平衡因子
}

4.3 新节点插入较高右子树的左侧—右左：先右单旋再左单旋（右左双旋）

思路：

右左双旋又分两大种情况：

一. h>=1的AVL树

1.在b处插入

2.在c处插入

二. h==0的AVL树

3. 60自己就是新增

是不是很简单？

并且我们可以直接复用之前的单旋

代码思路：

  • 将父节点的右孩子保存为subR，将subR的左孩子保存为subRL。
  • 获取subRL的平衡因子。
  • 对parent的右孩子进行右单旋操作。
  • 再对parent进行左单旋操作。
  • 根据subRL的平衡因子的不同情况，更新subRL、subR和parent的平衡因子。
//右左双旋
void RotateRL(Node* parent)
{
  Node* subR = parent->_right; // 将父节点的右孩子保存为subR
  Node* subRL = subR->_left;  // 将subR的左孩子保存为subRL
  int bf = subRL->_bf;   // 提前获取subRL的平衡因子
  RotateR(parent->_right);  // 对parent的右孩子进行右单旋操作
  RotateL(parent);   // 对parent进行左单旋操作
  if (bf == 0)   // 如果subRL的平衡因子为0
  {
    subRL->_bf = subR->_bf = parent->_bf = 0;  // 更新subRL、subR和parent的平衡因子为0
  }
  else if (bf == 1)  // 如果subRL的平衡因子为1
  {
    subRL->_bf = subR->_bf = 0; // 更新subRL和subR的平衡因子为0
    parent->_bf = -1;  // 更新parent的平衡因子为-1
  }
  else if (bf == -1)  // 如果subRL的平衡因子为-1
  {
    subRL->_bf = parent->_bf = 0;   // 更新subRL和parent的平衡因子为0
    subR->_bf = 1; // 更新subR的平衡因子为1
  }
  else
  {
    assert(false);   // 如果平衡因子不是0、1或-1，则抛出错误
  }
}

4.4 新节点插入较高左子树的右侧—左右：先左单旋再右单旋（左右双旋）

思路：

在b处插入：

在c处插入：

60就是新增节点

代码思路：

  • 将父节点的左孩子保存为subL，将subL的右孩子保存为subLR。
  • 获取subLR的平衡因子。
  • 对parent的左孩子进行左单旋操作。
  • 再对parent进行右单旋操作。
  • 根据subLR的平衡因子的不同情况，更新subLR、subL和parent的平衡因子。
//左右双旋
  void RotateLR(Node* parent)
  {
    Node* subL = parent->_left;  // 将父节点的左孩子保存为subL
    Node* subLR = subL->_right;  // 将subL的右孩子保存为subLR
    int bf = subLR->_bf; // 获取subLR的平衡因子
    RotateL(parent->_left); //对parent的左孩子进行左单旋操作
    RotateR(parent);  // 对parent进行右单旋操作
    if (bf == 0)  // 如果subLR的平衡因子为0
    {
      subLR->_bf = subL->_bf = parent->_bf = 0;  // 更新subLR、subL和parent的平衡因子为0
    }
    else if (bf == 1)    // 如果subLR的平衡因子为1
    {
      subLR->_bf = parent->_bf = 0;  // 更新subLR和parent的平衡因子为0
      subL->_bf = -1;  // 更新subL的平衡因子为-1
    }
    else if (bf == -1) // 如果subLR的平衡因子为-1
    {
      subLR->_bf = subL->_bf = 0;     // 更新subLR和subL的平衡因子为0
      parent->_bf = 1;     // 更新parent的平衡因子为1
    }
    else
    {
      assert(false);   // 如果平衡因子不是0、1或-1，则抛出错误
    }
  }

5. 整体代码:

注：加了一些简单的打印和判断平衡的代码

#pragma once
#include <iostream>
using namespace std;
#include <map>
#include <assert.h>
//struct默认权限是public
template <class K, class V>
struct AVLTreeNode
{
  AVLTreeNode<K,V>* _left;//左孩子节点
  AVLTreeNode<K,V>* _right;//右孩子节点
  AVLTreeNode<K,V>* _parent;//父亲节点
  pair<K, V> _kv; //存储键值对的pair对象，其中K表示键的类型，V表示值的类型。
  int _bf;//该节点的平衡因子：高度差
  AVLTreeNode(const pair<K, V>& kv)
    :_left(nullptr)
    , _right(nullptr)
    , _parent(nullptr)
    ,_kv(kv)
    ,_bf(0)
  {}
};
//class默认是private
template <class K,class V>
class AVLTree
{
typedef  AVLTreeNode<K, V> Node;
public:
  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->_left;
      }
      else if (kv.first > cur->_kv.first)
      {
        parent = cur;
        cur = cur->_right;
      }
      else
      {
        return false;
      }
    }
    cur = new Node(kv);
    if (kv.first < parent->_kv.first)
    {
      parent->_left = cur;
      cur->_parent = parent;
    }
    if (kv.first > parent->_kv.first)
    {
      parent->_right = cur;
      cur->_parent = parent;
    }
    ///
    //AVL的开始
    while (parent)
    {
      if (cur == parent->_left)
      {
        parent->_bf--;
      } 
      else
      {
        parent->_bf++;
      }
      //说明更新前是-1或者1，并且更新后父节点左右平衡，不用继续往上更新了
      if (parent->_bf == 0)
      {
        break;
      }
      //说明更新前bf是0，必须往上进行更新
      else if (parent->_bf == 1 || parent->_bf == -1)
      {
        cur = parent;
        parent = parent->_parent;
      }
      //说明更新前是-1或者1，并且更新后的子树违反了AVL树的规则，需要进行调整
      else if(parent->_bf == 2 || parent->_bf == -2)
      {
        //旋转（核心）
        if (parent->_bf == 2 && cur->_bf == 1)
        {
          //左单旋
          RotateL(parent);
        }
        else if (parent->_bf == -2 && cur->_bf == -1)
        {
          //右单旋
          RotateR(parent);
        }
        else if (parent->_bf == 2 && cur->_bf == -1)
        {
          //右左双旋
          RotateRL(parent);
        }
        else if (parent->_bf == -2 && cur->_bf == 1)
        {
          //左右双旋
          RotateLR(parent);
        }
        //1.旋转让这棵子树平衡了
        //2.降低了这棵子树的高度，恢复到和之前一样的高度，对上一层没有影响，不用更新了
        break;
      }
      else
      {
        assert(false);
      }
    }
    return true;
  }
  //左单旋
  //（1.父亲节点的右边等于右孩子的左边; 2.右孩子的左边等于父亲节点）
  //【把右孩子的左边给给父亲节点的右边; 2.再把父亲节点给给右孩子的左边】
  void RotateL(Node *parent)
  {
    Node* SubR = parent->_right;
    Node* SubRL = SubR->_left;
    //旋转链接
    parent->_right = SubRL;
    SubR->_left = parent;
    Node* Parent_Parent = parent->_parent;
    parent->_parent = SubR;
    if (SubRL)
    {
      SubRL->_parent = parent;
    }
    //和父节点的父节点链接
    if (_root == parent)
    {
      _root = SubR;
      SubR->_parent = nullptr;
    }
    else
    {
      if (Parent_Parent->_left == parent)
      {
        Parent_Parent->_left = SubR;
      }
      else
      {
        Parent_Parent->_right = SubR;
      }
      SubR->_parent = Parent_Parent;
    }
    //更新平衡因子
    SubR->_bf = parent->_bf = 0;
  }
  //右单旋
  void RotateR(Node* parent)
  {
    Node* SubL = parent->_left;
    Node* SubLR = SubL->_right;
    //旋转链接
    //动一个节点就把他的父亲也变动
    parent->_left = SubLR;
    if (SubLR)//SubLR可能为空
    {
      SubLR->_parent = parent;
    }
    Node* Parent_Parent = parent->_parent;
    SubL->_right = parent;
    parent->_parent = SubL; 
    //和父节点的父节点链接
    if (_root == parent)
    {
      _root = SubL;
      SubL->_parent = nullptr;
    }
    else
    {
      if (Parent_Parent->_left == parent)
      {
        Parent_Parent->_left = SubL;
      }
      else
      {
        Parent_Parent->_right = SubL;
      }
      SubL->_parent = Parent_Parent;//链接
    }
    SubL->_bf = parent->_bf = 0;
    //更新平衡因子
  }
  //右左双旋
  void RotateRL(Node *parent)
  {
    Node* subR = parent->_right;
    Node* subRL = subR->_left;
    int bf = subRL->_bf;
    RotateR(parent->_right);
    RotateL(parent);
    if (bf == 0)
    {
      subRL->_bf = subR->_bf = parent->_bf=0;
    }
    else if (bf == 1)
    {
      subRL->_bf = subR->_bf = 0;
      parent->_bf = -1;
    }
    else if (bf == -1)
    {
      subRL->_bf = parent->_bf = 0;
      subR->_bf = 1;
    }
    else
    {
      assert(false);
    }
  }
  //左右双旋
  void RotateLR(Node* parent)
  {
    Node* subL = parent->_left;
    Node* subLR = subL->_right;
    int bf = subLR->_bf;
    RotateL(parent->_left);
    RotateR(parent);
    if (bf == 0)
    {
      subLR->_bf = subL->_bf = parent->_bf = 0;
    }
    else if (bf == 1)
    {
      subLR->_bf = parent->_bf = 0;
      subL->_bf = -1;
    }
    else if (bf == -1)
    {
      subLR->_bf = subL->_bf = 0;
       parent->_bf= 1;
    }
    else
    {
      assert(false);
    }
  }
  void InOrder()
  {
    _InOrder(_root);
    cout << endl;
  }
  void _InOrder(Node* root)
  {
    if (root == nullptr)
      return;
    _InOrder(root->_left);
    cout << root->_kv.first << " ";
    _InOrder(root->_right);
  }
  //判断是否平衡
  bool IsBalance()
  {
    return _IsBalance(_root);
  }
  int _Height(Node* root)
  {
    if (root == nullptr)
      return 0;
    int leftHeight = _Height(root->_left);
    int rightHeight = _Height(root->_right);
    return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
  }
  bool _IsBalance(Node* root)
  {
    if (root == nullptr)
      return true;
    int leftHeight = _Height(root->_left);
    int rightHeight = _Height(root->_right);
    if (rightHeight - leftHeight != root->_bf)
    {
      cout << root->_kv.first << "平衡因子异常" << endl;
      return false;
    }
    return abs(rightHeight - leftHeight) < 2
      && _IsBalance(root->_left)
      && _IsBalance(root->_right);
  }
private:
  Node* _root = nullptr;
};

6. AVL树的验证

AVL树是在二叉搜索树的基础上加入了平衡性的限制，因此要验证AVL树，可以分两步：

1.验证其为二叉搜索树

  • 如果中序遍历可得到一个有序的序列，就说明为二叉搜索树
#include "AVLTree.h"
#include <vector>
int main()
{
  int arr[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };
  AVLTree<int, int> a;
  for (auto e : arr)
  {
    a.insert(make_pair(e, e));
  }
  a.InOrder();
  return 0;
}

2.验证其为平衡树

  • 每个节点子树高度差的绝对值不超过1(注意节点中如果没有平衡因子)
  • 节点的平衡因子是否计算正确

用下面代码判断是否为平衡树：

bool IsBalance()
{
  return _IsBalance(_root);  // 调用内部函数_IsBalance检查整个AVL树是否平衡
}
int _Height(Node* root)
{
  if (root == nullptr)  // 如果当前节点为空，表示到达叶子节点，返回高度0
    return 0;
  int leftHeight = _Height(root->_left);  // 递归计算左子树的高度
  int rightHeight = _Height(root->_right);  // 递归计算右子树的高度
  return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;   // 返回较大的子树高度加1，表示当前子树的高度
}
bool _IsBalance(Node* root)
{
  if (root == nullptr)    // 如果当前节点为空，表示到达叶子节点，返回true表示平衡
    return true;
  int leftHeight = _Height(root->_left);   // 计算左子树的高度
  int rightHeight = _Height(root->_right);  // 计算右子树的高度
  if (rightHeight - leftHeight != root->_bf)   // 判断右子树高度减去左子树高度是否等于当前节点的平衡因子
  {
    cout << root->_kv.first << "平衡因子异常" << endl;  // 如果不相等，输出异常信息
    return false;     // 返回false表示不平衡
  }
  return abs(rightHeight - leftHeight) < 2   // 判断当前子树的高度差是否小于2
    && _IsBalance(root->_left)   // 递归检查左子树是否平衡
    && _IsBalance(root->_right);    // 递归检查右子树是否平衡
}

代码解释：

  • _Height函数用于计算以给定节点为根的子树的高度，它递归地计算左子树和右子树的高度，然后返回较大的一侧高度加1，表示当前子树的高度。
  • _IsBalance函数是实际进行平衡性检查的函数，它首先判断当前节点是否为空，如果为空则表示到达叶子节点，返回true表示平衡。然后，它计算当前节点的左子树和右子树的高度，并判断其高度差是否等于当前节点的平衡因子。如果不相等，则输出异常信息并返回false表示不平衡。接着，它递归地检查左子树和右子树是否平衡，并判断当前子树的高度差是否小于2。如果所有条件都满足，则返回true表示平衡。
  • 通过调用IsBalance函数，可以判断整个AVL树是否平衡，即是否满足平衡因子的定义和高度差的限制。

代码测试：

int main()
{
  const int N = 30;
  vector<int> v;
  v.reserve(N);
  srand(time(0));
  for (size_t i = 0; i < N; i++)
  {
    v.push_back(rand() % 100 + 1);
  }
  AVLTree<int, int> t;
  for (auto e : v)
  {
    t.insert(make_pair(e, e));
  }
  t.InOrder();//中序打印
  if (t.IsBalance())
  {
    cout << "是平衡二叉树" << endl;
  }
  else
  {
    cout << "不是平衡二叉树" << endl;
  }
  return 0;
}

7. AVL树的性能

AVL树是一棵绝对平衡的二叉搜索树，其要求每个节点的左右子树高度差的绝对值都不超过1，这样可以保证查询时高效的时间复杂度，即l o g 2 ( N ) log_2 (N)log2(N)。但是如果要对AVL树做一些结构修改的操作，性能非常低下，比如：插入时要维护其绝对平衡，旋转的次数比较多，更差的是在删除时，有可能一直要让旋转持续到根的位置。因此：如果需要一种查询高效且有序的数据结构，而且数据的个数为静态的(即不会改变)，可以考虑AVL树，但一个结构经常修改，就不太适合。

（本章完）

文章标签：
容器
存储
originalHSL.
目录
相关文章
爱叨叨的小嘟
|
4天前
二叉树刷题记（十-1.二叉树的镜像-2.二叉搜索树中的搜索）大家一起学习呗
二叉树刷题记（十-1.二叉树的镜像-2.二叉搜索树中的搜索）大家一起学习呗
爱叨叨的小嘟
15 0
Dio夹心小面包
|
4天前
|
存储 C++ 索引
『 C++ 』AVL树详解 ( 万字 )
『 C++ 』AVL树详解 ( 万字 )
Dio夹心小面包
42 0
Dio夹心小面包
|
4天前
|
存储 C++
『 C++ 』红黑树RBTree详解 ( 万字 )
『 C++ 』红黑树RBTree详解 ( 万字 )
Dio夹心小面包
60 0
originalHSL.
|
5月前
|
算法 关系型数据库 调度
红黑树（万字图文详解）
红黑树（万字图文详解）
originalHSL.
43 1
水滴技术
|
11月前
|
存储 算法 Java
Java数据结构与算法分析（十）B树图文详解（含完整代码）
迄今为止，已经介绍了《 二叉查找树 》和《 AVL树 》，我们始终假设可以把整个数据结构存储在内存中。可是，如果数据多到内存装不下，这就意味着必须把数据放在磁盘上，显然这些数据结构不再适用。 问题在于磁盘的I/O速度是远远不如内存访问速度的，然而从一棵树中查找到某个元素，必须从根节点一层层往下找，这每一次查找便是一次I/O操作。为了提高性能，就必须要减少查找的次数。 如能减少树的高度、增加每个节点中的元素数，便是种有效的解决方案。实现这种想法的一种方法是使用B树。
水滴技术
82 0
Cyan_RA9
|
存储 算法 程序员
C 非线性结构——树 万字详解（通俗易懂）
C 数据结构与算法入门——树 内容分享。
Cyan_RA9
122 0
阿紫1
|
算法 C语言
数据结构与算法（十四）哈夫曼树
数据结构与算法（十四）哈夫曼树
阿紫1
116 0
前端歌谣
|
前端开发
前端知识案例-树的广度优先遍历
前端知识案例-树的广度优先遍历
前端歌谣
50 0
前端知识案例-树的广度优先遍历
洛神灬殇
|
算法 网络安全 C++
【数据结构之旅】「AVL平衡树专项」带你领略常用的AVL树与红黑树的奥秘（规则篇）
【数据结构之旅】「AVL平衡树专项」带你领略常用的AVL树与红黑树的奥秘（规则篇）
洛神灬殇
127 0
【数据结构之旅】「AVL平衡树专项」带你领略常用的AVL树与红黑树的奥秘（规则篇）
xgiw3kxo6j5o6
|
存储 算法 C++
【算法日记】—— 搜索二叉树
【算法日记】—— 搜索二叉树
xgiw3kxo6j5o6
101 0
【算法日记】—— 搜索二叉树

热门文章

最新文章

  • 1
    TCP三次握手与四次分手
  • 2
    袋鼠云数据中台专栏（五）：数栈，企业级一站式数据中台PaaS
  • 3
    利用Serverless Kubernetes和Kaniko快速自动化构建容器镜像
  • 4
    CentOS7(6.5)升级docker到较新版
  • 5
    如何判断自己IP是内网IP还是外网IP
  • 6
    模型社区实战训练营首开,开源让代码更有趣!
  • 7
    深入分析bgp选路规则(上)
  • 8
    2-Sat+输出可行解(个人模版)
  • 9
    一次ORA-00130: invalid listener address错误
  • 10
    PathFinding.js – 综合性的 JavaScript 路径查找库
  • 1
    AI大咖说-如何评价论文的创新性
    16
  • 2
    实时计算 Flink版产品使用合集之在Flink Stream API中，可以在任务启动时初始化一些静态的参数并将其存储在内存中吗
    16
  • 3
    实时计算 Flink版产品使用合集之支持在同步全量数据时使用checkpoint吗
    13
  • 4
    51.从键盘上输入任意两个数和一个运算符（+、-、*、/），根据输入的运算符对两个数计算，并输出结果
    13
  • 5
    50.编写程序，逆转字符串
    13
  • 6
    49.输入一字符串，检查是否回文 （回文是指正反序相同，如，LeveL）
    11
  • 7
    48.输入任意正整数，编程判断该数是否为回文数(回文数是指从左到右读与从右到左读一样，如12321）
    9
  • 8
    47.从键盘上输入一个3*3的矩阵，并求其主对角线元素的和
    10
  • 9
    46.编写程序在屏幕上显示如下图形
    8
  • 10
    45.将3×3二维数组转置，并输出
    12

    • 相关课程

    更多
  • 【算法实战】10. 树回归算法

    • 相关电子书

    更多
  • 图解算法小抄
  • 低代码开发师（初级）实战教程
  • 阿里巴巴DevOps 最佳实践手册
    • 下一篇
    2024年阿里云免费云服务器及学生云服务器申请教程参考