zor*_*rgo 4 algorithm binary-tree
任何人都可以请告诉我你怎么二分找到B树,2-3-4树和二叉搜索树的最小/最大高度？
谢谢.
PS:这不是功课.
小智 5
2-4棵树的最小和最大高度
对于2-4树的最大高度,我们将每个节点有一个密钥,因此它将表现得像二进制搜索树.
级别0 = 1的键
级别1 = 2的键
2级键= 4,依此类推....
在每个级别添加键的总数,我们得到GP解决,我们将得到树的最大高度.
因此,height = log 2(n + 1)-1
解决它总共10 ^ 6个键我们将得到:
⇒1*(2 ^ 0 + 2 ^ 1 + 2 ^ 2 + ... ... + 2 ^ h)= 10 ^ 6
⇒1*(2 ^(h + 1) - 1)= 10 ^ 6
⇒h= log 2(10 ^ 6 + 1) - 1
⇒2-4树的最大高度,总共10 ^ 6个键是19
对于2-4树的最小高度,我们将为每个节点提供三个密钥(最大可能的数量).
级别0 = 3的键
等级1 = 3*(4)
2级键= 3*(4 ^ 2),依此类推...
因此,height = log 4(n + 1)-1
在每个级别添加键的总数,我们将获得GP解决方案,我们将获得最小高度.解决它总共10 ^ 6个键我们得到:
⇒3*(4 ^ 0 + 4 ^ 1 + 4 ^ 2 + ... ... + 4 ^ h)= 10 ^ 6
⇒(4 ^(h + 1) - 1)= 10 ^ 6
⇒h= log 4(10 ^ 6 + 1) - 1
⇒2-4树的最小高度为9
二叉搜索树
对于最大高度,我们将有一个连续的长度为n的链(总节点数),因此给我们一个等于n-1的高度(高度从0开始).
对于最小高度,我们将有一个完美平衡的树,并且如前所述,我们将具有等于log 2(n + 1)-1的高度