首页
学习
活动
专区
圈层
工具
发布
  • 您找到你想要的搜索结果了吗?
    是的
    没有找到

    红黑树简介及左旋、右旋、变色

    四、红黑树的变色操作 当对红黑树进行插入或删除节点之后,如果不再完全满足红黑树的5条特性,除了旋转,变色也可以使二叉搜索树重新满足红黑树的5条特性。 变色:将节点的颜色由红变黑或由黑变红。...通过变色,先将节点20变成黑色,特性4满足了,但又不满足特性5,所以继续将节点30变成红色,节点40变成黑色。 ? 经过3次变色后,从局部看,已经重新满足了红黑树的特性。...通过变色,先将节点80变成黑色,但仍不满足特性5,继续将节点70变成红色,重新满足了红黑树的特性。 ? 经过两次变色,重新满足了红黑树的特性,对于这个例子,只要局部满足了,整棵树一定是满足红黑树的。...五、红黑树的旋转和变色综合案例 上文中介绍旋转和变色时,是独立对它们进行分析的。这两种调整方法都可以使被破坏规则的红黑树重新满足红黑树的特性,更多的时候,需要灵活地配合使用,使调整更高效。...经过变色,左旋,变色,三个步骤之后,插入节点后的树重新成为一棵红黑树。

    2.6K50
    领券