二叉树总结

待我称王封你为后i 2023-07-08 02:41 18阅读 0赞

### **1、二叉查找树** ###

1.  特点：二叉查找树的特点就是左子树的节点值比父亲节点小，而右子树的节点值比父亲节点大。如图：
2.  ![format_png][]
3.  查找：基于二叉查找树的这种特点，我们在查找某个节点的时候，可以采取类似于**二分查找**的思想，快速找到某个节点。
4.  时间复杂度：n 个节点的二叉查找树，正常的情况下，查找的时间复杂度为 **O（logn）。**之所以说是**正常情况下**，是因为二叉查找树有可能出现一种极端的情况，例如：
5.  ![format_png 1][]
6.  这种情况也是满足**二叉查找树**的条件，然而，此时的二叉查找树已经近似退化为一条链表，这样的二叉查找树的查找时间复杂度顿时变成了** O(n)**，可想而知，我们必须不能让这种情况发生，为了解决这个问题，于是我们引申出了**平衡二叉树**。

### **2、平衡二叉树** ###

1.  **特点：**平衡二叉树就是为了解决二叉查找树退化成一颗链表而诞生了，平衡树具有如下特点：1、具有二叉查找树的全部特性。2、每个节点的左子树和右子树的**高度差至多等于1**。
2.  例如：图一就是一颗平衡树了，而图二则不是(节点右边标的是这个节点的高度)
3.  ![format_png 2][]![format_png 3][]
4.  平衡树基于这种特点就可以保证不会出现大量节点偏向于一边的情况了。关于平衡树如何构建、插入、删除、左旋、右旋等操作这里不在说明，具体可以看这篇文章，[传送门][Link 1]

### **3、红黑树** ###

1.  红黑树出现的理由：虽然平衡树解决了二叉查找树退化为近似链表的缺点，能够把查找时间控制在 O(logn)，不过却不是最佳的，因为平衡树要求**每个节点的左子树和右子树的高度差至多等于1**，这个**要求实在是太严了**，导致每次进行插入/删除节点的时候，几乎都会破坏平衡树的第二个规则，进而我们都需要通过**左旋**和**右旋**来进行调整，使之再次成为一颗符合要求的平衡树。显然，如果在那种插入、删除很频繁的场景中，平衡树需要频繁着进行调整，这会使平衡树的性能大打折扣，为了解决这个问题，于是有了**红黑树**
2.  **特点：**
    
    1.  每个节点只有两种颜色：红色和黑色
    2.  根节点是黑色的
    3.  每个叶子节点都是黑色的空节点（NIL），也就是说，叶子节点不存数据。
    4.  从根节点到叶子节点，不会出现两个连续的红色节点
    5.  每个节点，从该节点到达其可达的叶子节点是所有路径，都包含相同数目的黑色节点。（主要保证了黑色节点的绝对平衡这是比平衡二叉树有优势的地方）
    6.  例如下面的图片（注意，图片中黑色的、空的叶子节点没有画出）（图片来自极客时间）
        
        1.  ![format_png 4][]
3.  **查找**：他的查找过程和二叉查找树一样，查找元素比当前节点大，就从右子树继续查找比较，查找元素比当前节点小，就从左子树继续查找比较。查找过程就不再赘述了。
4.  **插入**：红黑树插入是通过对节点的变色和旋转（左旋和右旋）进行调整的
    
    1.  不过，如果你要说，单单在查找方面的效率的话，平衡树比红黑树快。所以，我们也可以说，**红黑树是一种不大严格的平衡树**。因为它不是严格控制左、右子树高度或节点数之差小于等于1
    2.  与平衡树不同的是，红黑树在插入、删除等操作，**不会像平衡树那样，频繁着破坏红黑树的规则，所以不需要频繁着调整**，这也是我们为什么大多数情况下使用红黑树的原因。
    3.  正是由于红黑树的这种特点，使得它能够在最坏情况下，也能在 O(logn) 的时间复杂度查找到某个节点。
5.  **应用：**而关于红黑树的应用，一个非常经典的就是JDK1.8的HashMap中，当链表长度超过**8**时，就会由链表变成红黑树
6.  **总结**：平衡树是为了解决二叉查找树退化为链表的情况，而红黑树是为了解决平衡树在插入、删除等操作需要频繁调整的情况。
7.  **区别**：平衡二叉树（左旋右旋）和红黑树（左旋右旋和变色）插入时的算法差不多，那为什么还说红黑树的插入删除效率高呢？因为他也是通过左旋右旋来去保证树的平衡，所以感觉差不多呀？
    
    1.  **平衡二叉树追求的是绝对平衡！也就是说左子树和右子树差值必须小于等于1**
    2.  **红黑树保证弱平衡即可，不需要保证绝对平衡**
    3.  红黑树呢？首选不需要保证树高度的绝对平衡，只需要保证左右子树中的黑色节点数量一致即可，这只是保证了黑色节点的绝对平衡，红色节点是不考虑的也就是说左子树和右子树只要满足2倍以内的关系就可以了
    4.  **结论**：你要平衡二叉树的绝对平衡应该怎么搞？你要去遍历所有节点，去判断每个节点的左右子树的高度，之后再从这些失衡节点中选取最低的失衡节点。然后再去旋转blablabla。
    5.  红黑树呢？保证弱平衡即可。每次插入一个red节点，之后只需要看parent节点是不是red再来判断要不要调整，相比较来看对二叉树进行修改时，红黑树要简单一些。
8.  参考：[https://mp.weixin.qq.com/s/GgGfaIk379M9jHv0ZTgSHQ][https_mp.weixin.qq.com_s_GgGfaIk379M9jHv0ZTgSHQ]

[format_png]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9pbWcyMDE4LmNuYmxvZ3MuY29tL2Jsb2cvMTc1NzA4Mi8yMDE5MDgvMTc1NzA4Mi0yMDE5MDgyOTE2NTk0ODYzOC0xMTEyMjY3NzcyLnBuZw?x-oss-process=image/format,png
[format_png 1]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9pbWcyMDE4LmNuYmxvZ3MuY29tL2Jsb2cvMTc1NzA4Mi8yMDE5MDgvMTc1NzA4Mi0yMDE5MDgyOTE3MDEwODU2MS0zNDk2OTQ5MjYucG5n?x-oss-process=image/format,png
[format_png 2]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9pbWcyMDE4LmNuYmxvZ3MuY29tL2Jsb2cvMTc1NzA4Mi8yMDE5MDgvMTc1NzA4Mi0yMDE5MDgyOTE3MDMxNDI0MC0xODI1MTY1MTY5LnBuZw?x-oss-process=image/format,png
[format_png 3]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9pbWcyMDE4LmNuYmxvZ3MuY29tL2Jsb2cvMTc1NzA4Mi8yMDE5MDgvMTc1NzA4Mi0yMDE5MDgyOTE3MDM0NzM3MS0yMjc4NzMxNjMucG5n?x-oss-process=image/format,png
[Link 1]: https://mp.weixin.qq.com/s/dYP5-fM22BgM3viWg4V44A
[format_png 4]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9pbWcyMDE4LmNuYmxvZ3MuY29tL2Jsb2cvMTc1NzA4Mi8yMDE5MDgvMTc1NzA4Mi0yMDE5MDgyOTE3MDcwNjk0Ni0xNzI1ODU0NDU1LnBuZw?x-oss-process=image/format,png
[https_mp.weixin.qq.com_s_GgGfaIk379M9jHv0ZTgSHQ]: https://mp.weixin.qq.com/s/GgGfaIk379M9jHv0ZTgSHQ