二叉树总结

待我称王封你为后i 2023-07-08 02:41 83阅读 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 2format_png 3
  4. 平衡树基于这种特点就可以保证不会出现大量节点偏向于一边的情况了。关于平衡树如何构建、插入、删除、左旋、右旋等操作这里不在说明，具体可以看这篇文章，传送门

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

发表评论

表情：
评论列表 （有 0 条评论，83人围观）

还没有评论，来说两句吧...

相关阅读

    相关 二叉树基础知识总结

    题外话 昨晚面了腾讯，问了一个完全二叉树的题，竟然让我算了快10分钟，因为等比公式记错了导致最后用最原始的方法推算结果也没算对，一下子就懵了。本来精心准备了1周的面

    ﹏ヽ暗。殇╰゛Y﹏ヽ暗。殇╰゛Y/ 0 赞/ 289 阅读

    相关 二叉树知识点总结

    二叉树是一种比较重要的数据结构，这里对一些常见的二叉树的基础知识做一个总结，具体的代码实现放到下一篇博文 首选对二叉树进行一个分类，二叉树分为以下的几种:

    - 日理万妓- 日理万妓/ 0 赞/ 345 阅读