文章 2022-12-10 来自:开发者社区

C++ 第八节&数据结构 第七节 ——二叉搜索树 AVL树 红黑树(底层原理图+模拟实现)

目录1、二叉搜索树1-1、概念1-2 二叉搜索树的增、删、查1-2-1 二叉搜索树的增加(结点数据)1-2-2二叉搜索树的查找1-2-3 二叉搜索树的删除1-2-4  二叉搜索树的性能分析2、AVLTree2-1 AVLTree的概念2-1-1 左单旋:2-1-2 右单旋:2-1-3 左右单旋:2-2 总结:3、红黑树3-1 红黑树的概念:3-2 红黑树的性质:3-3 红黑树的调整3-....

C++ 第八节&数据结构 第七节 ——二叉搜索树 AVL树 红黑树(底层原理图+模拟实现)
文章 2022-04-21 来自:开发者社区

C++AVL树(3)

5、总结假如以pParent为根的子树不平衡,即pParent的平衡因子为2或者-2,分以下情况考虑:pParent的平衡因子为2,说明pParent的右子树高,设pParent的右子树的根为pSubR当SubR的平衡因子为1时,执行左单旋当SubR的平衡因子为-1时,执行右左双旋pParent的平衡因子为-2,说明pParent的左子树高,设pParent的左子树的根为pSubL当SubL的平....

文章 2022-04-21 来自:开发者社区

C++AVL树(2)

四、AVL树的旋转如果在一棵原本是平衡的AVL树中插入一个新节点,可能造成不平衡,此时必须调整树的结构,使之平衡根据节点插入位置的不同,AVL树的旋转分为四种:新节点插入较高右子树的右侧—右右:左单旋1、左单旋抽象示图:注意:上图在插入前AVL树是平衡的,新节点插入到60的右子树(注意:此处不是有孩子)中,60右子树增加了一层,导致以30为根的二叉树不平衡要让30平衡,只能将30右子树的高度减少....

文章 2022-04-21 来自:开发者社区

C++AVL树(1)

零、前言本章主要讲解map和set的底层结构平衡二叉搜索树的一种-AVL树的特性及其实现一、AVL树的概念引入:map/multimap/set/multiset其底层都是按照二叉搜索树来实现的,但是二叉搜索树有其自身的缺陷假如往树中插入的元素有序或者接近有序,二叉搜索树就会退化成单支树,时间复杂度会退化成O(N)因此map、set等关联式容器的底层结构是对二叉树进行了平衡处理,即采用平衡树来实....

本页面内关键词为智能算法引擎基于机器学习所生成,如有任何问题,可在页面下方点击"联系我们"与我们沟通。

开发与运维

集结各类场景实战经验,助你开发运维畅行无忧

+关注
AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等