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

c++的学习之路：26、AVL树

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

摘要

本章主要是说一下AVL树的实现，这里说的是插入的底层原理


一、原理


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


二叉搜索树虽可以缩短查找的效率，但如果数据有序或接近有序二叉搜索树将退化为单支树，查

找元素相当于在顺序表中搜索元素，效率低下。因此，两位俄罗斯的数学家G.M.Adelson-Velskii

和E.M.Landis在1962年发明了一种解决上述问题的方法：当向二叉搜索树中插入新结点后，如果能保证每个结点的左右子树高度之差的绝对值不超过1(需要对树中的结点进行调整)，即可降低树的高度，从而减少平均搜索长度。一棵AVL树或者是空树，或者是具有以下性质的二叉搜索树：它的左右子树都是AVL树，左右子树高度之差(简称平衡因子)的绝对值不超过1(-1/0/1)如果一棵二叉搜索树是高度平衡的，它就是AVL树。如果它有n个结点，其高度可保持在O(log_2 n)，搜索时间复杂度O(log_2 n)。


下面的图就是一颗AVL树，画的有点抽象，0、-1、1就是平衡因子


二、四种旋转

1、左单旋

如下图就是左单选的过程，就是b肯定是比30大，这时就可以把b连接到30的右边，然后把60变成根节点，30变成60的左节点，就是如下图这种变化，然后这时就需要进行更新平衡因子，就可以进行左旋了，电脑画图太麻烦了，我就放一下我的手图了。


2、右单旋

右单选，与做单选相反就是把右边的进行放在左边，然后原理都差不多，就是b的位置肯定是比60小然后就放到30左边，然后在进行旋转进行连接在，这样就可以右旋了，这里我就不画电脑的图了，用我的手图代替了

3、左右双旋


左右双旋就是先进行做单选在进行右单选，这种情况的形状就是<就是这种的就是一个小于号，当直接左旋或者右旋就会把树给扭曲了，就不是平衡了们就是先把他变成/这种形状然后在进行右单选就可以平衡这个二叉树了，下面就是我画的图了，就不用电脑画了。


4、右左双旋

这里就是和上面那个双旋相反，就是先把>这个形状变成\这种，然后就是先进行右单选，在进行做单选，就可以把这颗树进行平衡了，这里就不进行画图了，因为原理都差不多。


三、代码实现

1、节点创建

这个节点是利用三叉链进行维护的，数据存储也就是和搜索二叉树的原理，因为搜索二叉树会右歪脖子树，所以这里就只是平衡，但是他的原理还是差不多，所以这里也是利用键值对进行一个pair容器的创建，然后在创建一个bf进行充当平衡因子进行维护。


template<class K,class V>
struct AVLtreeNode//三叉链
{
    AVLtreeNode<K, V>* _left;//左孩子
    AVLtreeNode<K, V>* _right;//右孩子
    AVLtreeNode<K, V>* _parent;//父母节点
    pair<K, V> _kv;//键值对，用来存储数据
    int _bf;//平衡因子，用来平衡AVL树，使他相对像完全二叉树
    AVLtreeNode(const pair<K, V>& kv)
        :_left(nullptr)
        , _right(nullptr)
        , _parent(nullptr)
        , _kv(kv)
        , _bf(0)
    {}
};

2、插入


插入的代码就是和搜索二叉树原理差不多，也就是大于在右边小于在左边，这里创建也是先进行插入，没有节点的时候就插入在根，有的时候就去遍历寻找，大的在右边小的在左边，然后进行插入，在进行更新平衡因子，这里是利用一个节点记录当前的父节点时候，就可以进行循环进行更新平衡因子，等于2或者-2的时候就需要进行旋转了，这时有四种情况


1、父节点=2、当前节点=1就是进行左单旋


2、父节点=-2、当前节点=-1就是右单旋


3、父节点=2、当前节点=-1时，就是双旋了，左右双旋


4、父节点=-1、当前节点=1时，就是右左双旋


下方代码就是我写的插入，也有注释

bool Insert(const pair<K, V>& kv)
    {
        if (_root == nullptr)//如果是空节点直接申请，然后返回true
        {
            _root = new Node(kv);
            return true;
        }
        Node* parent = nullptr;//记录父节点
        Node* cur = _root;//记录当前节点
        while (cur)//遍历去寻找插入的地方
        {
            if (cur->_kv.first < kv.first)//大于就去左边寻找
            {
                parent = cur;
                cur = cur->_right;
            }
            else if (cur->_kv.first > kv.first)//大于就去右边寻找
            {
                parent = cur;
                cur = cur->_left;
            }
            else
            {
                return false;//找不到就返回false
            }
        }
        cur = new Node(kv);//创建新的节点
        if (parent->_kv.first > kv.first)//如果小于就插入在右边
        {
            parent->_left = cur;
        }
        else if (parent->_kv.first < kv.first)//如果大于就插入到左边
        {
            parent->_right = cur;
        }
        cur->_parent = parent;//记录一下父节点的地址
        while (parent)//平衡因子的更新，持续到根
        {
            if (cur == parent->_right)//判断新的节点在父节点的左右，如果在右边平衡因子就++，如果在左边就--
            {
                parent->_bf++;
            }
            else
            {
                parent->_bf--;
            }
            if (parent->_bf == 1 || parent->_bf == -1)//如果父节点的平衡因子等于1或者-1，接着更新
            {
                parent = parent->_parent;
                cur = cur->_parent;
            }
            else if(parent->_bf==0)//如果平衡因子等于0就退出
            {
                break;
            }
            else if (parent->_bf == 2 || parent->_bf == -2)//超长了，准备旋转了，有四种情况
            {
                if (parent->_bf == 2 && cur->_bf == 1)//当父节点的平衡因子等于2当前节点的平衡因子等于1时                
                {                                      //就是相当于右边是一条直线时，然后进行左旋
                    RotateL(parent);//调用左旋函数
                }
                else if (parent->_bf == -2 && cur->_bf == -1)//当父平衡因子等于-2当前节点平衡因子等于-1时
                {                                                //就是左边时一条直线的情况时，然后进行右旋
                    RotateR(parent);//调用右旋函数
                }
                else if (parent->_bf == -2 && cur->_bf == 1)//当父节点平衡因子等于-2时，当前节点的平衡因子等于-1时
                {                                            //就是相当于一条折现，就是<这个形状，需要旋转两次，先左旋在右旋
                    RotateLR(parent);//调用先左旋在右旋的函数
                }
                else if (parent -> _bf == 2 && cur->_bf == -1)//当父节点平衡因子等于2时，当前节点平衡因子等于-1时
                {                                            //就是相当于>这个形状，也是需要旋转两次，先进性右旋在进行左旋
                    RotateRL(parent);//调用先右旋在左旋的函数
                }
                else
                {
                    assert(false);//上述情况都没出现，就说明树已经出现问题了，这里直接利用断言直接报错，断死
                }
                break;
            }
            else
            {
                assert(false);//这里就是更新平衡因子失败，也就是说上述都没，也就是直接报错，因为树也是出现错误了
            }
        }
    return true;
    }

3、旋转

下面这段代码就是四种旋转，在左右单旋后，更新平衡因子是0，双旋的平衡因子需要根据具体条件具体实现，具体怎么是先把的下面都有注释。

void RotateL(Node* parent)//左旋
    {
        Node* subR = parent->_right;//记录父节点的右侧，用来后续旋转
        Node* subRL = subR->_left;//记录subR的左侧，这个节点比父节点大，比subR小
        parent->_right = subRL;//因为这个节点比父节点大，所以连接父节点在右边
        if (subRL)
            subRL->_parent = parent;//如果subRL节点不是空姐点就把他的父节点置为父节点
        Node* ppnode = parent->_parent;//记录父节点的父节点
        subR->_left = parent;//旋转把subR的左节点连接为父节点，因为父节点比subR节点小
        parent->_parent = subR;//把父节点的父节点置为subR
        if (ppnode == nullptr)//判断ppnode是否为空也就是之前的父节点是否为根
        {
            _root = subR;//如果是根的话，就把subR置为根，在把subR的父节点置为空
            _root->_parent = nullptr;
        }
        else
        {
            if (ppnode->_left == parent)//判断ppnode的左节点是否为之前的父节点，如果是就把位置换成subR
            {
                ppnode->_left = subR;
            }
            else
            {
                ppnode->_right = subR;//判断ppnode的右节点是否为之前的父节点，如果是就把位置换成subR
            }

            subR->_parent = ppnode;//在进行连接subR的父节点
        }
        parent->_bf = subR->_bf = 0;//最后更新平衡因子，因为旋转过后肯定是平衡的所以直接置为0
    }

    void RotateR(Node* parent)//右旋，与上面左旋的原理差不多，就是换个方向
    {
        Node* subL = parent->_left;
        Node* subLR = subL->_right;
        parent->_left = subLR;
        if (subLR)
            subLR->_parent = parent;
        Node* ppnode = parent->_parent;
        subL->_right = parent;
        parent->_parent = subL;
        if (parent == _root)
        {
            _root = subL;
            _root->_parent = nullptr;
        }
        else
        {
            if (ppnode->_left == parent)
            {
                ppnode->_left = subL;
            }
            else
            {
                ppnode->_right = subL;
            }
            subL->_parent = ppnode;
        }
        subL->_bf = parent->_bf = 0;
    }

    void RotateLR(Node* parent)//双旋之先左旋在右旋
    {
        Node* subL = parent->_left;//记录父节点的左侧
        Node* subLR = subL->_right;//记录subL的右侧因为形状是<这样的，然后需要先左旋进行掰直
        int bf = subLR->_bf;//用于记录平衡因子
        RotateL(parent->_left);//利用左旋函数进行左旋，这里就是把父节点的左侧当成父节点传进去，也就是subL
        RotateR(parent);//然后在进行右旋
        if (bf == 1)//更新平衡因子，当前平衡因子如果等于1就把父节点的平衡因子置为0，subLR的为0，因为这个节点在旋转过后
        {            //就会平衡，但是在bf等于1时，左边肯定是有的，所以subL就是-1
            parent->_bf = 0;
            subLR->_bf = 0;
            subL->_bf = -1;
        }
        else if (bf == -1) //在旋转之前平衡因子是-1 的话，在旋转结束时，也就是说明父节点的位置就是需要置为1，因为之前
        {                    //在左，旋转之后就是有右，其他两个就是0
            parent->_bf = 1;
            subLR->_bf = 0;
            subL->_bf = 0;
        }
        else if (bf == 0)//如果都是0的话旋转后也是0就直接更新成0
        {
            parent->_bf = 0;
            subLR->_bf = 0;
            subL->_bf = 0;
        }
        else//如果没有就说明树出现问题了直接断言报错
        {
            assert(false);
        }
    }

    void RotateRL(Node* parent)//现右旋在左旋与上面差不多
    {
        Node* subR = parent->_right;
        Node* subRL = subR->_left;
        int bf = subRL->_bf;
        RotateR(parent->_right);
        RotateL(parent);
        if (bf == 1)
        {
            subR->_bf = 0;
            parent->_bf = -1;
            subRL->_bf = 0;
        }
        else if (bf == -1)
        {
            subR->_bf = 1;
            parent->_bf = 0;
            subRL->_bf = 0;
        }
        else if (bf == 0)
        {
            subR->_bf = 0;
            parent->_bf = 0;
            subRL->_bf = 0;
        }
        else
        {
            assert(false);
        }
    }

4、判断是否平衡

这里还是进行一个封装，因为不太好穿私有变量，所以这里也就是利用函数进行封装了，如下方代码所示，是否出现错误就是判断高度差，也就是左右高度差不超过2，这里如下方代码所示，在代码旁边注释了了我的思路


void InOrder()
    {
        _InOrder(_root);
        cout << endl;
    }

    bool IsBalance()
    {
        return _IsBalance(_root);
    }

    int Height()
    {
        return _Height(_root);
    }
private:
    int _Height(Node* root)//求树的高度
    {
        if (root == NULL)
            return 0;
        int leftH = _Height(root->_left);
        int rightH = _Height(root->_right);
        return leftH > rightH ? leftH + 1 : rightH + 1;
    }

    bool _IsBalance(Node* root)//判断是否出现异常，高度差在2以内
    {
        if (root == NULL)
        {
            return true;
        }
        int leftH = _Height(root->_left);
        int rightH = _Height(root->_right);
        if (rightH - leftH != root->_bf)//判断平衡因子是否出错
        {
            cout << root->_kv.first << "节点平衡因子异常" << endl;
            return false;
        }
        return abs(leftH - rightH) < 2//这里是因为不知道哪个大所以直接求绝对值
            && _IsBalance(root->_left)//因为每条路都需要求一下所以直接递归去求
            && _IsBalance(root->_right);
    }

    void _InOrder(Node* root)//中序遍历
    {
        if (root == nullptr)
        {
            return;
        }
        _InOrder(root->_left);
        cout << root->_kv.first << " ";
        _InOrder(root->_right);
    }

5、测试

这里是利用随机数进行测试是否是平衡，如下方代码和测试结果。

void test()
{
    srand(time(0));
    const size_t N = 500000;
    AVLTree<int, int> t;
    for (size_t i = 0; i < N; ++i)
    {
        size_t x = rand() + i;
        t.Insert(make_pair(x, x));
        //cout << t.IsBalance() << endl;
    }

    //t.Inorder();

    cout << t.IsBalance() << endl;
    cout << t.Height() << endl;
}

四、代码

#pragma once
 
template<class K,class V>
struct AVLtreeNode//三叉链
{
  AVLtreeNode<K, V>* _left;//左孩子
  AVLtreeNode<K, V>* _right;//右孩子
  AVLtreeNode<K, V>* _parent;//父母节点
  pair<K, V> _kv;//键值对，用来存储数据
  int _bf;//平衡因子，用来平衡AVL树，使他相对像完全二叉树
  AVLtreeNode(const pair<K, V>& kv)
    :_left(nullptr)
    , _right(nullptr)
    , _parent(nullptr)
    , _kv(kv)
    , _bf(0)
  {}
};
 
template<class K,class V>
class AVLTree
{
  typedef AVLtreeNode<K,V> Node;//重定义，方便后续节点申请使用
public:
  bool Insert(const pair<K, V>& kv)
  {
    if (_root == nullptr)//如果是空节点直接申请，然后返回true
    {
      _root = new Node(kv);
      return true;
    }
    Node* parent = nullptr;//记录父节点
    Node* cur = _root;//记录当前节点
    while (cur)//遍历去寻找插入的地方
    {
      if (cur->_kv.first < kv.first)//大于就去左边寻找
      {
        parent = cur;
        cur = cur->_right;
      }
      else if (cur->_kv.first > kv.first)//大于就去右边寻找
      {
        parent = cur;
        cur = cur->_left;
      }
      else
      {
        return false;//找不到就返回false
      }
    }
    cur = new Node(kv);//创建新的节点
    if (parent->_kv.first > kv.first)//如果小于就插入在右边
    {
      parent->_left = cur;
    }
    else if (parent->_kv.first < kv.first)//如果大于就插入到左边
    {
      parent->_right = cur;
    }
    cur->_parent = parent;//记录一下父节点的地址
    while (parent)//平衡因子的更新，持续到根
    {
      if (cur == parent->_right)//判断新的节点在父节点的左右，如果在右边平衡因子就++，如果在左边就--
      {
        parent->_bf++;
      }
      else
      {
        parent->_bf--;
      }
      if (parent->_bf == 1 || parent->_bf == -1)//如果父节点的平衡因子等于1或者-1，接着更新
      {
        parent = parent->_parent;
        cur = cur->_parent;
      }
      else if(parent->_bf==0)//如果平衡因子等于0就退出
      {
        break;
      }
      else if (parent->_bf == 2 || parent->_bf == -2)//超长了，准备旋转了，有四种情况
      {
        if (parent->_bf == 2 && cur->_bf == 1)//当父节点的平衡因子等于2当前节点的平衡因子等于1时       
        {                   //就是相当于右边是一条直线时，然后进行左旋
          RotateL(parent);//调用左旋函数
        }
        else if (parent->_bf == -2 && cur->_bf == -1)//当父平衡因子等于-2当前节点平衡因子等于-1时
        {                       //就是左边时一条直线的情况时，然后进行右旋
          RotateR(parent);//调用右旋函数
        }
        else if (parent->_bf == -2 && cur->_bf == 1)//当父节点平衡因子等于-2时，当前节点的平衡因子等于-1时
        {                     //就是相当于一条折现，就是<这个形状，需要旋转两次，先左旋在右旋
          RotateLR(parent);//调用先左旋在右旋的函数
        }
        else if (parent -> _bf == 2 && cur->_bf == -1)//当父节点平衡因子等于2时，当前节点平衡因子等于-1时
        {                     //就是相当于>这个形状，也是需要旋转两次，先进性右旋在进行左旋
          RotateRL(parent);//调用先右旋在左旋的函数
        }
        else
        {
          assert(false);//上述情况都没出现，就说明树已经出现问题了，这里直接利用断言直接报错，断死
        }
        break;
      }
      else
      {
        assert(false);//这里就是更新平衡因子失败，也就是说上述都没，也就是直接报错，因为树也是出现错误了
      }
    }
  return true;
  }
 
  void InOrder()
  {
    _InOrder(_root);
    cout << endl;
  }
 
  bool IsBalance()
  {
    return _IsBalance(_root);
  }
 
  int Height()
  {
    return _Height(_root);
  }
private:
  int _Height(Node* root)//求树的高度
  {
    if (root == NULL)
      return 0;
    int leftH = _Height(root->_left);
    int rightH = _Height(root->_right);
    return leftH > rightH ? leftH + 1 : rightH + 1;
  }
 
  bool _IsBalance(Node* root)//判断是否出现异常，高度差在2以内
  {
    if (root == NULL)
    {
      return true;
    }
    int leftH = _Height(root->_left);
    int rightH = _Height(root->_right);
    if (rightH - leftH != root->_bf)//判断平衡因子是否出错
    {
      cout << root->_kv.first << "节点平衡因子异常" << endl;
      return false;
    }
    return abs(leftH - rightH) < 2//这里是因为不知道哪个大所以直接求绝对值
      && _IsBalance(root->_left)//因为每条路都需要求一下所以直接递归去求
      && _IsBalance(root->_right);
  }
 
  void _InOrder(Node* root)//中序遍历
  {
    if (root == nullptr)
    {
      return;
    }
    _InOrder(root->_left);
    cout << root->_kv.first << " ";
    _InOrder(root->_right);
  }
  void RotateL(Node* parent)//左旋
  {
    Node* subR = parent->_right;//记录父节点的右侧，用来后续旋转
    Node* subRL = subR->_left;//记录subR的左侧，这个节点比父节点大，比subR小
    parent->_right = subRL;//因为这个节点比父节点大，所以连接父节点在右边
    if (subRL)
      subRL->_parent = parent;//如果subRL节点不是空姐点就把他的父节点置为父节点
    Node* ppnode = parent->_parent;//记录父节点的父节点
    subR->_left = parent;//旋转把subR的左节点连接为父节点，因为父节点比subR节点小
    parent->_parent = subR;//把父节点的父节点置为subR
    if (ppnode == nullptr)//判断ppnode是否为空也就是之前的父节点是否为根
    {
      _root = subR;//如果是根的话，就把subR置为根，在把subR的父节点置为空
      _root->_parent = nullptr;
    }
    else
    {
      if (ppnode->_left == parent)//判断ppnode的左节点是否为之前的父节点，如果是就把位置换成subR
      {
        ppnode->_left = subR;
      }
      else
      {
        ppnode->_right = subR;//判断ppnode的右节点是否为之前的父节点，如果是就把位置换成subR
      }
 
      subR->_parent = ppnode;//在进行连接subR的父节点
    }
    parent->_bf = subR->_bf = 0;//最后更新平衡因子，因为旋转过后肯定是平衡的所以直接置为0
  }
 
  void RotateR(Node* parent)//右旋，与上面左旋的原理差不多，就是换个方向
  {
    Node* subL = parent->_left;
    Node* subLR = subL->_right;
    parent->_left = subLR;
    if (subLR)
      subLR->_parent = parent;
    Node* ppnode = parent->_parent;
    subL->_right = parent;
    parent->_parent = subL;
    if (parent == _root)
    {
      _root = subL;
      _root->_parent = nullptr;
    }
    else
    {
      if (ppnode->_left == parent)
      {
        ppnode->_left = subL;
      }
      else
      {
        ppnode->_right = subL;
      }
      subL->_parent = ppnode;
    }
    subL->_bf = parent->_bf = 0;
  }
 
  void RotateLR(Node* parent)//双旋之先左旋在右旋
  {
    Node* subL = parent->_left;//记录父节点的左侧
    Node* subLR = subL->_right;//记录subL的右侧因为形状是<这样的，然后需要先左旋进行掰直
    int bf = subLR->_bf;//用于记录平衡因子
    RotateL(parent->_left);//利用左旋函数进行左旋，这里就是把父节点的左侧当成父节点传进去，也就是subL
    RotateR(parent);//然后在进行右旋
    if (bf == 1)//更新平衡因子，当前平衡因子如果等于1就把父节点的平衡因子置为0，subLR的为0，因为这个节点在旋转过后
    {     //就会平衡，但是在bf等于1时，左边肯定是有的，所以subL就是-1
      parent->_bf = 0;
      subLR->_bf = 0;
      subL->_bf = -1;
    }
    else if (bf == -1) //在旋转之前平衡因子是-1 的话，在旋转结束时，也就是说明父节点的位置就是需要置为1，因为之前
    {         //在左，旋转之后就是有右，其他两个就是0
      parent->_bf = 1;
      subLR->_bf = 0;
      subL->_bf = 0;
    }
    else if (bf == 0)//如果都是0的话旋转后也是0就直接更新成0
    {
      parent->_bf = 0;
      subLR->_bf = 0;
      subL->_bf = 0;
    }
    else//如果没有就说明树出现问题了直接断言报错
    {
      assert(false);
    }
  }
 
  void RotateRL(Node* parent)//现右旋在左旋与上面差不多
  {
    Node* subR = parent->_right;
    Node* subRL = subR->_left;
    int bf = subRL->_bf;
    RotateR(parent->_right);
    RotateL(parent);
    if (bf == 1)
    {
      subR->_bf = 0;
      parent->_bf = -1;
      subRL->_bf = 0;
    }
    else if (bf == -1)
    {
      subR->_bf = 1;
      parent->_bf = 0;
      subRL->_bf = 0;
    }
    else if (bf == 0)
    {
      subR->_bf = 0;
      parent->_bf = 0;
      subRL->_bf = 0;
    }
    else
    {
      assert(false);
    }
  }
  Node* _root = nullptr;
};
 
void test()
{
  srand(time(0));
  const size_t N = 500000;
  AVLTree<int, int> t;
  for (size_t i = 0; i < N; ++i)
  {
    size_t x = rand() + i;
    t.Insert(make_pair(x, x));
    //cout << t.IsBalance() << endl;
  }
 
  //t.Inorder();
 
  cout << t.IsBalance() << endl;
  cout << t.Height() << endl;
}


文章标签：
C++
容器
存储
关键词：
C++ avl树
C++ avl
C++学习
C++学习树
懒懒学c
目录
相关文章
是乙太呀
|
6天前
|
算法 网络安全 区块链
2023/11/10学习记录-C/C++对称分组加密DES
本文介绍了对称分组加密的常见算法（如DES、3DES、AES和国密SM4）及其应用场景，包括文件和视频加密、比特币私钥加密、消息和配置项加密及SSL通信加密。文章还详细展示了如何使用异或实现一个简易的对称加密算法，并通过示例代码演示了DES算法在ECB和CBC模式下的加密和解密过程，以及如何封装DES实现CBC和ECB的PKCS7Padding分块填充。
是乙太呀
27 4
2023/11/10学习记录-C/C++对称分组加密DES
土木林森
|
4月前
|
算法 C语言 C++
C++语言学习指南：从新手到高手，一文带你领略系统编程的巅峰技艺！
【8月更文挑战第22天】C++由Bjarne Stroustrup于1985年创立，凭借卓越性能与灵活性，在系统编程、游戏开发等领域占据重要地位。它继承了C语言的高效性，并引入面向对象编程，使代码更模块化易管理。C++支持基本语法如变量声明与控制结构；通过`iostream`库实现输入输出；利用类与对象实现面向对象编程；提供模板增强代码复用性；具备异常处理机制确保程序健壮性；C++11引入现代化特性简化编程；标准模板库(STL)支持高效编程；多线程支持利用多核优势。虽然学习曲线陡峭，但掌握后可开启高性能编程大门。随着新标准如C++20的发展，C++持续演进，提供更多开发可能性。
土木林森
92 0
chian-ocean
|
28天前
|
存储 C++
【C++】AVL树
AVL树是一种自平衡二叉搜索树，由Georgy Adelson-Velsky和Evgenii Landis提出。它通过确保任意节点的两子树高度差不超过1来维持平衡，支持高效插入、删除和查找操作，时间复杂度为O(log n)。AVL树通过四种旋转操作（左旋、右旋、左-右旋、右-左旋）来恢复树的平衡状态，适用于需要频繁进行数据操作的场景。
chian-ocean
40 2
梦笔生花伟
|
2月前
|
编译器 C语言 C++
配置C++的学习环境
【10月更文挑战第18天】如果想要学习C++语言，那就需要配置必要的环境和相关的软件，才可以帮助自己更好的掌握语法知识。 一、本地环境设置 如果您想要设置 C++ 语言环境，您需要确保电脑上有以下两款可用的软件，文本编辑器和 C++ 编译器。 二、文本编辑器 通过编辑器创建的文件通常称为源文件，源文件包含程序源代码。 C++ 程序的源文件通常使用扩展名 .cpp、.cp 或 .c。 在开始编程之前，请确保您有一个文本编辑器，且有足够的经验来编写一个计算机程序，然后把它保存在一个文件中，编译并执行它。 Visual Studio Code：虽然它是一个通用的文本编辑器，但它有很多插
梦笔生花伟
64 6
nanshaws
|
2月前
|
Java 编译器 C++
c++学习，和友元函数
本文讨论了C++中的友元函数、继承规则、运算符重载以及内存管理的重要性，并提到了指针在C++中的强大功能和使用时需要注意的问题。
nanshaws
28 1
源码星辰
|
3月前
|
存储 C++
【C++】AVL树
AVL树是一种自平衡二叉搜索树：它以苏联科学家Georgy Adelson-Velsky和Evgenii Landis的名字命名。
源码星辰
32 2
枫叶丹4
|
4月前
|
C++ 容器
【C++航海王：追寻罗杰的编程之路】关联式容器的底层结构——AVL树
【C++航海王：追寻罗杰的编程之路】关联式容器的底层结构——AVL树
枫叶丹4
44 5
დ旧言~
|
5月前
|
C++
【C++】手撕AVL树（下）
【C++】手撕AVL树（下）
დ旧言~
60 1
ephemerals__
|
26天前
|
存储 编译器 C语言
【c++丨STL】string类的使用
本文介绍了C++中`string`类的基本概念及其主要接口。`string`类在C++标准库中扮演着重要角色，它提供了比C语言中字符串处理函数更丰富、安全和便捷的功能。文章详细讲解了`string`类的构造函数、赋值运算符、容量管理接口、元素访问及遍历方法、字符串修改操作、字符串运算接口、常量成员和非成员函数等内容。通过实例演示了如何使用这些接口进行字符串的创建、修改、查找和比较等操作，帮助读者更好地理解和掌握`string`类的应用。
ephemerals__
42 2
ephemerals__
|
1月前
|
存储 编译器 C++
【c++】类和对象（下）（取地址运算符重载、深究构造函数、类型转换、static修饰成员、友元、内部类、匿名对象）
本文介绍了C++中类和对象的高级特性，包括取地址运算符重载、构造函数的初始化列表、类型转换、static修饰成员、友元、内部类及匿名对象等内容。文章详细解释了每个概念的使用方法和注意事项，帮助读者深入了解C++面向对象编程的核心机制。
ephemerals__
84 5