侧边栏壁纸
  • 累计撰写 793 篇文章
  • 累计创建 1 个标签
  • 累计收到 1 条评论
标签搜索

目 录CONTENT

文章目录

红黑树

Dettan
2021-04-10 / 0 评论 / 0 点赞 / 166 阅读 / 404 字
温馨提示:
本文最后更新于 2022-07-23,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。
自平衡二叉查找树,典型的用途是实现关联数组。

红黑树是一种特化的AVL树(平衡二叉树),都是在进行插入和删除操作时通过特定操作保持二叉查找树的平衡,从而获得较高的查找性能。

可以在O(log n)时间内做查找,插入和删除,这里的n 是树中元素的数目。

平均统计性能要强于 AVL

查找时可以当成普通二叉排序树
每一个子树也是红黑树


性质
1.
根结点是黑色。 
2.
结点是红色或黑色。 
3.
所有叶子都是黑色。(叶子是NIL结点) (不存储数据的节点,可以忽略)
4.
每个红色结点的两个子结点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色结点)
5.
从任一节结点其每个叶子的所有路径都包含相同数目的黑色结点。 
这些约束强制了红黑树的关键性质: 从根到叶子的最长的可能路径不多于最短的可能路径的两倍长。结果是这个树大致上是平衡的。
是性质4导致路径上不能有两个连续的红色结点确保了这个结果。最短的可能路径都是黑色结点,最长的可能路径有交替的红色和黑色结点。

0

评论区