您现在的位置是:首页 > 技术文章网站首页技术文章

红黑树与平衡二叉树

  • WangYe
  • 2020-07-31 23:07:34
  • 495 次阅读
红黑树二叉树理解

红黑树性质:
    1.节点是红色或黑色;
    2.根节点是黑色;
    3.每个叶子节点都是黑色的空节点(NIL节点);
    4.每个红色节点的俩个子节点都是黑色。(从每个叶子到根的所有路径上不能有俩个连续的红色节点)
    5.从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点;

平衡二叉树(AVL)性质:
    1.一颗空树或左右俩个子树高度差绝对值不超过1,且左右俩个子树都是平衡的二叉树;
    2.把插入/查找/删除的时间复杂度最好情况和最坏情况维持再O(logN);
    3.相对二叉查找树来说,时间上稳定了很多;

区别:
    1.红黑树放弃了追求完全平衡,追求大致平衡,在与平衡二叉树的时间复杂度相差不大的情况下,
保证每次插入最多只需要三次旋转就能达到平衡,实现起来更为简单;
    2.平衡二叉树追求绝对平衡,条件苛刻,实现起来比较麻烦,每次插入新节点之后需要旋转的次数不能预知;

旋转和颜色变化规则:
    1.添加的节点必须为红色;
    2.变色的情况:当前节点的父是红色,且它的祖父节点的另一个节点也是红色:
        2.1 把父节点设置为黑色;
        2.2 把叔节点设置为黑色;
        2.3 把祖父节点设置为红色;
        2.4 把当前指针定义到祖父节点,设为当前要操作的
    3.左旋的情况:当前父节点是红色,叔节点是黑色,且当前的节点是右子树:
        3.1 以父节点作为左旋;
    4.右旋的情况:当前父节点是红色,叔节点是黑色,且当前的节点是左子树;
        4.1 把父节点变成黑色;
        4.2 把祖父节点变成红色
        4.3 以祖父节点右旋转;

上一篇:robots.txt的10种写法

下一篇:Socket多线程

文章评论 (0)



Top