当前位置: 首页>>数据结构与算法>> 阅读正文

数据结构之红黑树

Category: 数据结构与算法 View: 42,266 Author: Dong
, ,

  • 评论 (9)
  • 引用通告 (0)
发表评论 发起引用

  • 1楼路人甲 回复

    Post: 2011-08-29 18:41

    删除节点那一段:
    (1)S是红色的
    此时P肯定是红色的。

    此处应该是P肯定是黑色的吧,因为它的子S是红色。

    [回复]

  • 2楼397090770 回复

    Post: 2012-09-27 01:55

    3.2 删除操作
    删除操作可以概括为以下几个步骤:
    (1) 查找要删除位置,时间复杂度为:O(N)

    这里的时间复杂度是不是错了?既然和二叉查找树类似,那查找时间复杂度就应该为O(logn).

    [回复]

  • 3楼zh 回复

    Post: 2013-01-21 09:14

    感谢你的博客,我觉得比wiki上写的好,把各种处理情况归纳的很清晰。

    (2) 用删除节点后继或者节点替换该节点

    这地方写错了

    [回复]

  • 4楼zh 回复

    Post: 2013-01-21 09:41

    (1)S是红色的
    此时P肯定是红色的。

    此处应为P肯定是黑色的。

    [回复]

  • 5楼zh 回复

    Post: 2013-01-21 09:49

    因为删除 N 的初始的父亲使通过 N 的所有路径少了一个黑色节点,这使事情都平衡了起来。

    这句话是什么意思,要删除的不是N节点吗?

    [回复]

    jbingqiang 回复:

    1. 对于上述4中情况,是发生在节点已经删除(保证是二叉查找数),维持红黑树性质的阶段(通过重绘节点颜色或旋转)。因此,N是已经删除节点的后继节点,并非将要删除的节点;
    2. 对于情况2: 首先,以N为参考节点,S变为红色,使的S树的黑色深度减1,而N树的黑色深度也已经减1,因为已经删除的N的父节点是黑的。这样P树的黑色深度减1,然后,以P为参考节点,重复以上操作。

    注意对递归思想的理解。

    [回复]

    jbingqiang 回复:

    3. 情况4的本质是:把S的黑色给N的祖先,这使得N树的黑色深度加1, SR由红变黑,相当于S的右子树的黑色深度没有变化,从而维持整棵树的红黑性质。

    [回复]

  • 6楼zh 回复

    Post: 2013-01-21 10:00

    “如果需要删除的节点有两个儿子,那么问题可以被转化成删除另一个只有一个儿子的节点的问题。”

    如果图示都是照这一句来画,则N不可能是有两个非叶子节点的节点,这样的话图就有些小问题。

    还有个小问题,文中的意思是删除N的操作都是在转化到case 4之后做的吗?

    [回复]

  • 7楼Zhang 回复

    Post: 2013-06-28 02:08

    被删除节点的后继节点最多有一个非叶子节点,如果N是这个非叶子节点,为什么N还有1,2两个节点呢

    [回复]

  • 8楼zhe 回复

    Post: 2013-12-30 14:26

    照搬wiki都可以?!

    [回复]

  • 9楼thinkstream 回复

    Post: 2014-06-11 08:33

    总结的很到位

    [回复]

目前还没有任何Trackbacks和Pingbacks.
发表评论