知识卡片
极值节点不一定是叶子
在普通二叉搜索树中,从根一直沿left直到没有左孩子,得到最小键;沿right直到没有右孩子,得到最大键。该节点仍可能有另一侧孩子,所以原文“最左/最右叶子”不够准确。
工作量为O(h),h是树高;退化树最坏O(n),有对数高度界时为O(log n),而不是所有平衡方案都严格至多log n个节点。若使用本章隐藏删除实现,还需排除hidden节点,不能只按物理最左/右节点就当逻辑极值。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- · 查看原书依据
最小结点是最左边的那个叶子结点。要定位到该结点,从根结点开始通过左指针逐层下降,直到到达该分支的边缘。在非平衡的二叉搜索树中,在最坏的情况下这需要O(n)的时间,n代表树中的结点个数。这种情况发生在该树只有一个单独的左分支时。但是,如果保持树的平衡性,则没有哪一个分支将超过lg n个结点的长度,因而
参考来源
- 位置:《算法精解:C语言描述》第9章《问与答》(spine1306;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1273.html;u168-ch09-027)。
- 结论依据:168极值问答全文实读,节点可有相反方向孩子为BST定义直接反例;普通BST与159隐藏实现区别明确。
- 原始内容:最小结点是最左边的那个叶子结点。要定位到该结点,从根结点开始通过左指针逐层下降,直到到达该分支的边缘。在非平衡的二叉搜索树中,在最坏的情况下这需要O(n)的时间,n代表树中的结点个数。这种情况发生在该树只有一个单独的左分支时。但是,如果保持树的平衡性,则没有哪一个分支将超过lg n个结点的长度,因而