文章 2024-05-22 来自:开发者社区

【C++】map&set的底层结构 -- AVL树(高度平衡二叉搜索树)(下)

【C++】map&set的底层结构 -- AVL树(高度平衡二叉搜索树)(上)https://developer.aliyun.com/article/1515237?spm=a2c6h.13148508.setting.29.11104f0e63xoTy (2)新节点插入较高右子树的右侧 —— 右右:左单旋 ...

【C++】map&set的底层结构 -- AVL树(高度平衡二叉搜索树)(下)
文章 2024-05-22 来自:开发者社区

【C++】map&set的底层结构 -- AVL树(高度平衡二叉搜索树)(上)

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

【C++】map&set的底层结构 -- AVL树(高度平衡二叉搜索树)(上)

C++ 入门教程开发文档

42 课时 |
18000 人已学 |
免费
开发者课程背景图
文章 2023-05-23 来自:开发者社区

【C++】set和map的底层AVL树的实现(下)

下面我们再看h==1的情况: h==1有两种情况,要不在60的左树插入,要不在60的右树插入,不同的是如果插入在60的左树那么parent的平衡因子会变成1,其他两个节点的平衡因子还是0.当插入的节点在60的右边,那么只有subL的平衡因子变成-1,其他的平衡因子变成0࿰...

【C++】set和map的底层AVL树的实现(下)
文章 2023-05-23 来自:开发者社区

【C++】set和map的底层AVL树的实现(上)

前言上一篇文章对 map/multimap/set/multiset 进行了简单的介绍,在其文档介绍中发现,这几个容器有个共同点是:其底层都是按照二叉搜索树来实现的 ,但是二叉搜索树有其自身的缺陷,假如往树中插入的元素有序或者接近有序,二叉搜索树就会退化成单支树,时间复杂度会退化成 O(N) &#x...

【C++】set和map的底层AVL树的实现(上)

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