部分源码如上，我们通过源码可以看到源码中rb_tree使用了泛型思维实现；其中rb_tree是实现key搜索场景还是实现key/value的搜索场景不是写死的，...

红黑树作为一种自平衡的二叉搜索树，是计算机科学中的经典数据结构之一，广泛应用于各种需要高效查找、插入和删除操作的场景中，比如STL中的 map 和 set。虽然...

说明：下图中假设我们把新增结点标识为c(cur)，c的⽗亲标识为p(parent)，p的⽗亲标识为g(grandfather)，p的兄弟标识为u（uncle）。

在AVL树中，旋转是为了保持树的平衡性。AVL树是一种自平衡的二叉搜索树，它要求每个节点的左右子树的高度差不能超过1。当插入或删除节点后，可能会导致树的平衡因子...

AVL树（Adelson-Velsky and Landis Tree）是一种自平衡二叉查找树，它的特点是每个节点的左子树和右子树的高度差不能超过1。这意味着A...

相比较于AVL树，红黑树也是一个自平衡二叉搜索树，但是它与AVL树控制平衡的方式不同；

本文编写于 165 天前，最后修改于 159 天前，其中某些信息可能已经过时。

​ 简单来说，AVL树就是一个特殊的搜索二叉树，特殊就特殊在它可以控制平衡，保持左右子树的高度差不超过1。

说明: 下图中假设我们把新增结点标识为c (cur)，c的父亲标识为p (parent)，p的父亲标识为g (grandfather)，p的兄弟标识为u (un...

更新停止条件： 5. 更新后parent的平衡因子等于0，更新中parent的平衡因子变化为-1->0 或者 1->0，说明更新前parent子树一边高一边低...

AVL树是一种自平衡的二叉查找树（BST），由G.M. Adelson-Velsky和E.M. Landis于1962年提出。AVL树的核心特点是它保证树的每个...

​ 我们这里只实现红黑树的插入和删除，了解他们的底层即可，而后面我们在介绍 map 以及 set 的模拟实现的时候，我们就会进一步将红黑树进行改造！

​ 之前对 map / multimap / set / multiset 进行了简单的介绍，在其文档介绍中发现，这几个容器有个共同点是：其底层都是按照二叉搜索...

AVL树是最先发明的自平衡二叉查找树。在AVL树中，任何节点的两个子树的高度最大差别为1，所以它也被称为高度平衡树

如上图所示， parent和uncle都是红色，grandfather为黑色，此时插入新节点cur，出现连续红色节点。这种情况下，将parent和uncle变黑...

然后最后我们到了50这个位置处的节点后再++，就相当于找不到下一个了，也就是总数根节点的parent指针就是nullptr，因此后面我们把end()设计成nul...

首先可以把它理解成一颗二叉搜索树，但是它的节点会有颜色不是红就是黑，可以这么理解：就是avl树把平衡因子去掉并改成颜色再加以修改，但是平衡还是有点差别，高度可能...

这里我们可以看出来，就是把pr的左指针指向parent，parent的右指针指向pr1，但是这里就忽视了最终要的父亲指针，此时也要注意，把pr1（注意是否为空）...

这里比较简单，就是找比这个节点值大就往右走，小就往左走，直到走到空，就可以开辟节点并插入，但是问题就是连接起来，因此需要保存上一个也就是parent节点：

数组建堆，首尾交换，交换后的堆尾数据从堆中删掉，将堆顶数据向下调整选出次大的数据。