C++搜索二叉树，平衡二叉树，红黑树原理

AVL树的概念
一个树的根节点比左子树的大，比右子树的小。这就是搜索二叉树

但是我们对数据进行有序插入的时候，效率很低很低。

我们知道搜索二叉树影响搜索次数的是树的高度，那么我们就要想办法把树变平衡

接下来就是平衡二叉树
当向二叉搜索树中插入新结点后，如果能保证每个结点的左右子树高度之差的绝对值不超过1(需要对树中的结点进行调整)，即可降低树的高度，从而减少平均搜索长度。
我们要理解最终要的就是旋转
旋转呢又和平衡因子脱不了干系？

我们先理清插入的步骤
1 ，找到空闲位置
2 ，调节平衡因子
插入平衡因子的调节主要有以下几种情况（平衡因子的大小是右子树的高度-左子树的高度）

1 插入在节点得左边
父节点得平衡因子–；
2 插在右边，
父节点平衡因子加加；
然后根据平衡因子再来旋转。
当父节点得平衡因子为0得时候
父节点往上都不用修改
这种情况就是类似：

当节点为1或者-1 的时候
就一直向上调整（同样的也是判断假如的节点事左边还是右边，左边–，右边++，一直到根节点）

当节点的平衡因子更新为2或者-2 的时候，就需要考虑旋转了

分为4种
第一种LL形状（）
在这里我们是哪个节点的平衡因子被破坏了。根节点是不是。我们是在根节点的左边的左边插入的一个节点导致了这个不平衡。这种就被称为ll形


然后再把cur和parent的平衡因子改为0；并且将此情况丢定义为右旋（高右低）

RR的情况类似
LR的情况

RL类似

红黑树
红黑树，是一种二叉搜索树，但在每个结点上增加一个存储位表示结点的颜色，可以是Red或Black。 通过对任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路径会比其他路径长出俩倍，因而是接近平衡的。

4.2.2 红黑树的性质

1. 每个结点不是红色就是黑色
2. 根节点是黑色的
3. 如果一个节点是红色的，则它的两个孩子结点是黑色的
4. 对于每个结点，从该结点到其所有后代叶结点的简单路径上，均 包含相同数目的黑色结点
5. 每个叶子结点都是黑色的(此处的叶子结点指的是空结点)

新节点的吗，默认颜色是黑色
插入的步骤
6. 按照二叉搜索的树规则插入新节点
2 更改颜色
**
**

情况二: cur为红，p为红，g为黑，u不存在/u存在且为黑

![在这里插入图