当前位置：首页 > news >正文

查缺补漏----数据结构树高总结

news 2025/7/23 1:30:06

① 对于平衡二叉树而言，树高的规律：

高度为h的平衡二叉树的含有的最少结点数（所有非叶节点的平衡因子均为1）：

n0=1，n1=1，n2=2

$n_h=n_{h-1}+n_{h-2}+1$

含有的最多结点数：

$2^h-1$ (高度为h的满二叉树含有的结点数)

② 对于折半查找判定树树高：(和完全二叉树相同)

n= $\left \lfloor log_2{n} \right \rfloor+1$ 或者 $\left \lceil log_2{(n+1)} \right \rceil$

③ 对于二叉排序树的树高：

最大为n，最小： $\left \lceil log_2{(n+1)} \right \rceil$

④ 红黑树的树高的性质：

1.从根节点到叶节点的最长路径不大于最短路径的2倍。

这是每条路径上的黑结点相同，并且不能出现相邻的红节点导致的。

2.红黑树中任何左子树和右子树的高度差，不会超过两倍。

3.若根节点黑高为h，内部结点数(关键字)最少 $2^h-1$ 个。（满树的结点数）

4.若红黑树总高度=h，则根节点黑高>=h/2，因为不能出现相邻的两个红节点。又因为内部节点数 $n\geq 2^{\frac{h}{2}}-1$ ，所以： $h\leq 2log_{2}(n+1)$

⑤ 对于B树：m表示阶数

最小高度：

若要让B树的高度最小，在关键字数量不变的情况下，应该让每棵树尽可能满。对于m阶B树而言，每个结点最多有m-1个关键字以及m个分叉，则：

最大高度：

最大高度---让各层的分叉尽可能的少，即根节点只有2个分叉，其他结点只有个分叉。各层结点至少有：第一层 1、第二层 2、第三层.... 第h层，第h+1层共有叶子结点(失败结点)：个（第h+1层是叶子结点，则该树有h层）。

为什么n个关键字的B树有n+1个叶子结点？因为n个关键字把(-∞,+∞)分为了n+1个区域，这n+1个区域对应n+1种失败的情况，即n+1个失败节点（叶子结点）。