红黑树

红黑树知识点

红黑树五大定义：

  1. 节点颜色有红色和黑色

  2. 根节点必须为黑色

    2-3 树中如果根节点为 2 节点，那么他本来就对应红黑树中黑色节点，如果根节点为3 节点，也可以用黑色节点表示较大的那个元素，然后较小的元素作为左倾红节点存在于红黑树中

  3. 所有叶子节点都是黑色

  4. 任意节点到叶子节点经过的黑色节点数目相同

    红黑树中的红节点是和黑色父节点绑定的，在 2-3 树中本来就是同一层，只有黑色节点才会在 2-3 树中真正贡献高度，由于 2-3 树的任一节点到空链接的距离相同，因此反应在红黑树中就是黑色完美平衡

  5. 不会有连续的红色节点

    2-3 树中本来就规定没有 4 节点，2-3-4 树中虽然有 4 节点，但是要求在红黑树中体现为一黑色节点带两个红色儿子，分布左右，所以也不会有连续红节点

关于树的旋转

​ 为了调平一颗二叉树，使其左右节点数据分布均匀，通常会选择旋转的手段。可以把一颗二叉树某节点的左右子树想象成天平上待称量的物品，如果那边重了，我们就从重的那边拿出一部分，放到轻的那边，以此保持相对的平均。

旋转是二叉树调平的精髓

简单理解：

  • 左旋就是旋转点的右节点上升，同时将旋转点作为子节点挂载到右节点左边

  • 右旋就是旋转点的左节点上升，同时将旋转点作为子节点挂载到左节点右边

image-20201105101451656

image-20201105101508405

https://mp.weixin.qq.com/s/sPIE54UmvNgINZIATQKyew