前言
在二叉树的基础上，为了让搜索更加快捷，出现的二叉搜索树，二叉搜索树规定，二叉树的左子树的值一定都小于其父亲节点的值，所有右子树的值一定都大于其父亲节点的值，这样就保证了在查找某一个数据时，让时间复杂度最低为变为log n。
一、二叉树
两种特殊的二叉树
1.满二叉树
满二叉树每层的节点数都是满的，有2^(n-1)个节点，n表示层数，n>=1。如下图
2.完全二叉树
完全二叉树前n层的节点数都是满的，最后一层的节点数可能是满的，也可能不是满的，但是最后一层的节点一定是连续的。如下图
3.二叉树的性质
对于任意一颗二叉树而言，有如下性质。
每个节点的孩子节点数等于该节点的度数，每个节点的度数只可能是0，1，2。
叶子节点：没有孩子节点的节点被称为叶子节点，叶子节点的度为0。
记N0为度数为0的节点总数，N1为度数为1的节点总数，N2为度数为2的节点总数，N为二叉树的总节点数，则有
N=N0+N1+N2（和节点数相关）
N=总度数+1（和度数相关）
4.完全二叉树的性质
度为1的节点数要么是0，要么是1。
N1=0时，N=N0+N2=总度数+1=2N2
N1=1时，N=N0+N2+1=总度数+1=2N2+1
二、二叉搜索树
1.什么是二叉搜索树
二叉搜索树首先是一颗二叉树，在二叉树的前提下，又添加了如下的限制。
每个节点的值一定大于该节点左子树中所有节点的值，一定小于该节点右子树所有节点的值。而这会使得二叉搜索树的搜索效率大大提高。
2.二叉搜索树的优缺点
当二叉搜索数趋于一颗满二叉树或者完全二叉树时，它的搜索效率会很高。
但当二叉树只有一个枝叶时，搜索效率又会很差。
4.AVL树
为了使得二叉搜索树的搜索效率不会出现只朝着一端生长的极端情况，在搜索二叉树的前提下，对其加以限制，让搜索二叉树趋向满二叉树或者完全二叉树，使得搜索效率保持最优，这样的树被称为AVL树。
4.1AVL树的限制条件
1.每个节点的左右子树的高度差不超过1
2.每个节点都是AVL树
4.2AVL树如何保证搜索效率趋于最优
普通二叉树搜索效率最差时的情况。如下图
当所有节点都在某一枝上时，节点数就是搜索次数。原因就是，左右子树的高度差在不断增大。
当二叉搜索树是满二叉树时的搜索效率。
每搜索到一个节点，只可能选择该节点的左枝或者是右枝，而一旦进入某一枝，另一枝上所有的节点就已经被排除，不会被搜索。
当二叉搜索树是完全二叉树是的搜索效率和满二叉树类似。如下图
也就是说，二叉树越接近满二叉树，每次搜索时，就可以淘汰越多的节点。而AVL树的限制条件就是为了让他更趋于满二叉树。
5.红黑树
红黑树的本质也是一颗二叉搜索树，也是和AVL树一样在二叉搜索树的基础上加以限制。只是两者的限制方式不同，并且红黑树的限制条件没有AVL数那么严格，但是效率依然很高。
5.1红黑树的限制条件
1.每个节点都有颜色，要么是红色，要么是黑色，但是根节点的颜色一定是黑色。
2.黑节点的孩子节点可以是红色，也可以是黑色，但是红色节点的孩子节点一定是黑色。后者保证的是不可能有两个连续的红色节点。
3.红黑树的叶子节点是空节点，也就是说，空节点才是最后的节点，每个叶子节点的孩子节点都是空节点，空节点才是真正的叶子节点
4.从每个节点开始，到达其叶子节点的所有路径，每条路径上的黑色节点数是相同的。
6.二叉搜索树的应用
K结构和KV结构
K结构的二叉树，每个节点当中储存的就是一个值
而KV结构的二叉树，每个节点当中存储的是一个键值对
每个key对应的有一个value，就像是英汉字典当中的对应关系一样，根据
三、二叉搜索树的模拟实现
1.节点的模拟实现
二叉树的存储模型是一个个节点，节点中分为值域和指针域，值域用来存储值，指针域来分别指向当前节点的孩子节点。如下图
2.成员变量的模拟实现
只需要一个指向二叉树的根节点的指针即可，如果二叉树为空，则指针置为空即可，不需要动态开辟空间。如下图
3.插入算法的模拟实现
二叉搜索树的插入很简单。
先找到插入位置，再动态开辟空间，最后链接关系即可。如下图
4.删除算法的模拟实现
二叉搜索树的删除分为两种情况。
4.1只有一个孩子节点
当被删除节点只有一个孩子节点时，用孩子节点取代被删除节点。
删除节点有左孩子，没有右孩子。如下图
删除节点有右孩子，没有左孩子。如下图
4.2两个孩子节点
当被删除节点有两个孩子节点时，不能直接删除。
解决方法是从删除节点的左子树中找最大值当作替代节点，交换替代节点和删除节点的值后，删除替代节点的值即可，而替代节点一定只有一个孩子，更改链接关系即可。
4.3实现代码
四、AVL树的模拟实现
KV结构的AVL树的模拟实现
1.节点的模拟实现
AVL树需要限制左右子树的高度差，所以用_bf表示当前节点左右子树的高度差。
同时，AVL树的每个节点不仅指向左右孩子，还指向了自己的父亲节点。
2.成员变量的模拟实现
和普通二叉搜索树一样，AVL树的成员变量只有指向根节点的指针，为空树时，将指针置空即可，不需要动态开辟空间。如下图
3.插入算法的模拟实现
首先是找合适的插入位置插入，并建立链接关系，和普通的搜索二叉树相比，只是多了父亲节点关系的链接。如下图
插入的操作结束之后，需要更新平衡因子。
4.平衡因子的检查与调整
更新完平衡因子，最重要的是检查平衡因子。AVL树必须满足左右子树的高度差不超过1，也就是说，平衡因子的绝对值大于等于0，小于等于1。
如何判断是否需要调整平衡因子
插入数据后，更新的是插入节点的父亲的平衡因子，我们最先检查的也是父亲节点的平衡因子。而父亲的平衡因子可以分为两种情况，需要调整和不需要调整。
情况一：
父亲节点更新后的平衡因子如果等于0，则说明，原本父亲节点左右子树的高度差为1，现在虽然变为0，但是并不会向上造成影响，因为以父亲节点为根节点的子树的高度并没有发生变化，所以不会对上一层造成影响。所以情况一无需做出调整。
如下图
情况二：
父亲节点更新后的平衡因子如果等于+1或者-1，则说明，原来父亲节点左右子树的高度差为0，变为1后，以父亲节点为根节点的子树的高度差发生了变化，所以会改变父亲节点的父亲的平衡因子，也就是说改变上一层节点的平衡因子，此时需要向上判断。在向上判断中，依旧可能遇到三种情况中的任何一种。如下图
情况三：
父亲节点更新后的平衡因子如果等于+2或者-2，说明父亲节点此时已经需要调整。如下图
平衡因子的更新以及调整都是在一个循环中。因为情况二会导致某颗子树的高度发生变化，进而影响其他节点的平衡因子。每次循环都需要先更新平衡因子，再对三种情况进行分别讨论。如下图
情况一和情况二的处理很简单，只有情况三需要立即进行调整。
3.如何调整平衡因子
需要调整平衡因子的本质是，节点左右子树的高度差超过了1，所以调整平衡因子，就是要降低树的高度，降低树的高度的办法我们称之为旋转。
4.旋转算法
AVL树的旋转有四种情况，左单旋，右单旋，左右双旋和右左双旋。
旋转的目的就是降低树的高度，但在旋转过后，需要重新建立节点之间的平衡因子，以及重新赋予新的平衡因子。
左单旋
代码如下
右单旋
代码如下
左右双旋
代码如下
右左双旋
代码如下
5.AVL树的验证
判断每个节点的左右子树高度差是否满足AVL树即可。如下图
五、红黑树的模拟实现
1.节点的模拟实现
红黑树的存储模型和链表类似，是一个个节点。
红黑树的节点之间关系有三层，所以每个节点里存储了指向父亲节点、左孩子节点和右孩子节点的指针。
红黑树真正要存储的当然是数据，也就是某个值，但除此之外，还需要控制节点的颜色，关于颜色，利用枚举再合适不过。
如下图
1.1节点的默认颜色
节点的构造函数实现的是，对于每个新增节点，指针都置为空，节点的颜色都是红色。那为什么要将节点的默认颜色设置为红色？
如果将节点的默认颜色设置为黑色，那么除了空节点时的情况。在其他情况下，在某一条路径上多出一个黑色节点，必然会导致每条路径上的黑色节点数目不再相同，这就违反了红黑树的规则。
并且，一个黑色节点，会对整棵树都产生影响。但是红色节点不会，即使也可能出现连续的红色节点需要进行调整，但更有可能的是，刚好插入节点的父亲节点是黑色，也就不需要进行调整。
2.成员变量的模拟
和链表一样，红黑树本身存储的是指向树的根节点的一个指针，如果是空树，将指针置空即可，无需动态开辟空间。如下图
3.红黑树插入算法的模拟
2.1红黑树的插入
因为红黑树节点的默认颜色是红色，这就一定会导致，新插入节点的父亲节点的颜色也可能是红色，从而违反了红黑树的规则，也就需要进行调整。
也就是说，如果需要节点，必然是出现了两个连续的红节点，基于只可能出现两个红节点，也就意味着，如果新插入节点的父亲是红色节点，那父亲的父亲，暂且称为祖父，祖父节点的颜色一定是黑色。
也就是说，如果需要调整，那么插入节点，父亲节点，祖父节点的颜色一定是确定的。
2.2插入时的三种情况
情况一：插入节点和父亲节点为红色，祖父节点为黑色。父亲的兄弟节点，我们将其称为uncle，该节点如果存在且为黑。
解决方案：
将父亲和叔叔的节点颜色变为黑色，祖父的颜色变为红色。再将祖父当成新插入节点，进行判断。如下图
变色保证了，从祖父到父亲和叔叔的这两条路径上的黑色节点数没有变化，同时，从根节点到父亲和叔叔的这两条路径上的黑色节点数没有发生变化。也就是说通过变色解决了当前出现两个连续红色节点的问题。但是将祖父由黑色变为红色，而祖父的父亲也可能是红色，从而导致连锁问题，所以需要将祖父当作新插入节点，继续判断，一直到根节点。
并且，情况一中的祖父节点一定是存在的。这是因为，只有当父亲节点是根节点的时候，祖父节点才会不存在，而根节点的颜色又一定是黑色，而不会是红色，所以当情况一发生时祖父节点一定存在且为黑。
情况二：插入节点和父亲节点为红色，祖父节点为黑色。且叔叔不存在。
这种情况不能通过变色来解决问题，因为一旦变色，黑色节点数一定会发生变化，从而破坏红黑树的规则。这种情况，需要通过旋转加变色解决问题。需要旋转的几个节点是祖父，父亲。如下图
情况三：插入节点和父亲节点为红色，祖父节点为黑色。叔叔存在且为黑。
这种情况也不能通过变色来解决问题，因为也会导致黑色节点数的变化。所以也只能通过旋转加变色解决问题。需要旋转的几个节点是祖父，父亲，叔叔。
需要注意的是，发生情况一时，需要继续向上判断，继续向上判断时，可能会遇到情况一，情况二，情况三中的任何一种，如果是前者，则还需要继续向上判断，如果是情况二和情况三，在调整完成之后，就不需要继续向上判断，这是因为。
旋转加变色的最终，一定是将旋转后的父亲节点变为黑色，父亲节点的两个孩子变为红色，也只有这样才能继续保持每条路径上的黑色节点数相同。
2.3插入的代码实现
红黑树插入的前半部分和普通二叉搜索树的插入相同，都是寻找合适的插入位置，然后动态开辟节点空间，最后建立链接关系。而红黑树还有其他规则的限制，所以还需要在插入结束后进行检查和调整。如下图
解析：情况二和情况三的解决方法相同，都是旋转+变色，其实是一类问题
整个检查的过程是一个循环，因为情况一只进行变色，可能会向上造成影响。
因为要判断是哪一种旋转，所以需要清楚插入节点，插入节点的父亲节点以及祖父节点的位置关系。同时判断叔叔的情况属于哪一种。
最后将根节点的颜色变为空，是因为情况一中的祖父可能就是根节点，而整棵树的根节点必须是黑色。
2.4旋转的代码实现
左旋。如下图
右旋
4.获取树的高度
5.红黑树的验证
只需要检查三点
1.根节点是否是黑色。
2.是否有连续的红色节点。
3.每条路径的黑色节点数是否相同。
如下图
代码分析：
连续红节点的问题在CheckColor中的第三个If语句中检查，因为孩子节点可能会有两个，检查起来更麻烦，所以选择检查当前节点以及当前节点的父亲节点。
IsBalance中，根节点的问题一个if语句就可以搞定。
每条路径上的黑色节点数，是先计算了最左路径上黑色节点的数目，将其当作判断的依据，也就是基准值。如果其他路径上的黑色节点数都和它相同，则代表没有问题。
CheckColor在递归检查颜色的问题时，如果当前节点是黑色，会对黑色节点数++，并且会将当前节点的黑色节点数和基准值一起传入下一次循环，
当遇到空节点时，此时的黑色节点数在经过一次次的++和传入下一个递归，已经是当前路径上的黑色节点总数了，此时再和基准值进行比较。
标签：黑树,黑色,C++,二叉,AVL,插入,搜索,二叉树,节点 From： https://blog.51cto.com/u_15466618/8475110