qq_19684951 2019-09-25 10:12 采纳率: 25%
浏览 894

关于红黑树数据结构的一个基础问题

学习红黑树的过程中,发现了一个结论说:

最深叶子节点的深度不会大于两倍的最浅叶子节点的深度。

对这一个结论及其解释无法理解,请问什么为什么规定了是两倍呢?

平衡二叉树的定义是左右子树的高度差不过1,假如最深的叶子节点深度为10,那么
最浅的叶子节点顶多为9吧?难道还会有6,7,8等可能?

对于其解释过程中,说树的最长路径为红黑交替节点路径,最短路径只包含黑色节点。
请问最短路径为什么会只包含黑色节点呢?红黑树的定义中,如果一个节点为红色,那么他的子节点都是黑色,怎么会有全是黑色的路径呢?

请求教导,谢谢!!

  • 写回答

2条回答 默认 最新

  • zqbnqsdsmd 2019-09-25 10:29
    关注
    评论

报告相同问题?

悬赏问题

  • ¥60 版本过低apk如何修改可以兼容新的安卓系统
  • ¥25 由IPR导致的DRIVER_POWER_STATE_FAILURE蓝屏
  • ¥50 有数据,怎么建立模型求影响全要素生产率的因素
  • ¥50 有数据,怎么用matlab求全要素生产率
  • ¥15 TI的insta-spin例程
  • ¥15 完成下列问题完成下列问题
  • ¥15 C#算法问题, 不知道怎么处理这个数据的转换
  • ¥15 YoloV5 第三方库的版本对照问题
  • ¥15 请完成下列相关问题!
  • ¥15 drone 推送镜像时候 purge: true 推送完毕后没有删除对应的镜像,手动拷贝到服务器执行结果正确在样才能让指令自动执行成功删除对应镜像,如何解决?