一文搞懂二叉搜索树、B树、B+树、AVL树、红黑树( 四 ) _搜索树

文章插图
最后添加180到结点中，首先添加到160的右子结点，父结点和叔叔结点都变色为黑色，祖父结点150变成红色。

文章插图
变色

文章插图
右旋变成红色后，这种为第四种情况，即150结点的父结点是红色，叔叔结点是黑色，因此本例中需要右旋，由于右旋后200和160会碰撞，因此160结点的子树将作为200结点的左子树。

文章插图
左旋需要以200结点的祖父结点50为支点左旋，由于左旋后，50和100会发生碰撞，因此100将挂在50结点的右边。并且父结点150变成黑色，祖父结点50会变成红色。

文章插图
变色

文章插图
红黑树插入自平衡总结

N为根：涂黑完事；
父黑：啥事不用管；
父红叔红：父/叔涂黑，祖父涂红，然后把祖父当成新的平衡节点递归处理（我们下面平衡了，让他老人家和上面沟通吧）；
父红叔黑：父节点和新插入节点同一边的话，扭一下就完事了（同左右旋，同右左旋，顺便涂色）；不在同一边的话，先扭到同一边吧。

红黑树的删除红黑树的删除情况相对插入会复杂一些，这这里先不过多的介绍了，肝不动了。如果感兴趣的话，我们在来一起探讨~~
二叉搜索树、B树、B+树、AVL树、红黑树的常见面试题1 为什么设计红黑树红黑树通过它规则的设定，确保了插入和删除的最坏的时间复杂度是O(log N)。
红黑树解决了AVL平衡二叉树的维护起来比较麻烦的问题，红黑树，读取略逊于AVL，维护强于AVL，每次插入和删除的平均旋转次数应该是远小于平衡树。
因此：相对于要求严格的AVL树来说，红黑树的旋转次数少，所以对于插入、删除操作较多的情况下，我们就用红黑树。但是，只是对查找要求较高,那么AVL还是较优于红黑树.
2 B树、B+树和红黑树的区别

最大的区别就是树的深度较高，在磁盘I/O方面的表现不如B树。
在大规模数据存储的时候，红黑树往往出现由于树的深度过大而造成磁盘IO读写过于频繁，进而导致效率低下。在这方面，B树表现相对优异，B树可以有多个子女，从几十到上千，可以降低树的高度。
红黑树多用在内部排序，即全放在内存中的，STL的map和set的内部实现就是红黑树。
B+树多用于外存上时，B+也被成为一个磁盘友好的数据结构。

3 AVL树和红黑树的区别红黑树的算法时间复杂度和AVL相同，但统计性能比AVL树更高。
红黑树和AVL树都能够以O(log2 n)的时间复杂度进行搜索、插入、删除操作。2、由于设计，红黑树的任何不平衡都会在三次旋转之内解决。AVL树增加和删除可能需要通过一次或多次树旋转来重新平衡这个树。
在查找方面：红黑树的性质(最长路径长度不超过最短路径长度的2倍)，其查找代价基本维持在O(logN)左右，但在最差情况下(最长路径是最短路径的2倍少1)，比AVL要略逊色一点。AVL是严格平衡的二叉查找树（平衡因子不超过1）。查找过程中不会出现最差情况的单支树。因此查找效率最好，最坏情况都是O(logN)数量级的。
所以，综上： AVL比RBtree更加平衡，但是AVL的插入和删除会带来大量的旋转。所以如果插入和删除比较多的情况，应该使用RBtree, 如果查询操作比较多，应该使用AVL 。
4 数据库为什么使用B树，而不使用AVL或者红黑树我们假设B+树一个节点可以有100个关键字，那么3层的B树可以容纳大概1000000多个关键字（100+101100+101101*100）。而红黑树要存储这么多至少要20层。所以使用B树相对于红黑树和AVL可以减少IO操作
5 为什么B+树比B树更为友好