7.4.1.2 B 树的高度

教材导航 · 第7章

原书定位

印刷页P312起,对应PDF第324页。下文为目视整理的知识提要;完整内容见原书对照。

设 n≥1n\ge1 个关键字,hh 为实际结点层数,t=⌈m/2⌉t=\lceil m/2\rceil:

2th−1−1≤n≤mh−12t^{h-1}-1\le n\le m^h-1 ⌈log⁡m(n+1)⌉≤h≤⌊log⁡tn+12⌋+1\lceil\log_m(n+1)\rceil\le h\le\left\lfloor\log_t\frac{n+1}{2}\right\rfloor+1

右式来自根至少分成两路、其他层至少 tt 路。nn 个关键字对应 n+1n+1 个空失败子树位置。求实际结点数与求关键字数是不同问题,一个结点可容多个关键字。

对应练习

7.4 节习题与逐题解析

关联知识

原书对照

展开原书对照截图

原书对照,原书P312,PDF第324页