arrays - 如何计算具有一定高度的二叉搜索树的数组大小？

Question

我正在使用数组进行二叉搜索树实现。我需要为具有特定高度的 BST 创建一个数组。我如何计算这个尺寸？

Answer 1

我想，您正在谈论像在二进制堆中那样的索引实现。

存储在数组中的所有顶点。该数组的第一个元素 - 根。如果 BST 的某个顶点是数组的第 i 个元素，它的左子存储在索引为 2*i 的单元格中，右子存储在索引为 2*i+1 的单元格中。内存中这种表示的方案如下所示：

您正在询问某个给定高度的树大小。高度 - 是树中的多个级别。换句话说，高度是从根到任何叶子的路径长度。在上图中，BST 的高度 = 2。

如何计算数组大小以存储固定高度的树？这只是几何级数的总和。height = 0 的级别有 1 个元素，height=1 的下一级有 2 个元素，下一级有 4 个元素，依此类推。高度 = H 的级别有 2^H 元素。

用于存储高度 = H 的树的数组大小足以存储从 0 到 H 的所有级别：
2^0 // 高度 = 0
+
2 ^ 1 级别的单元格 // 高度 = 1 级别的单元
+...
+2^H = 2^(H+1)-1 ;

重要提示 - 许多编程语言都有从零开始的数组索引。因此，当您声明数组时，int tree[2^(H+1)-1]这意味着元素编号从 0 到 2^(H+1)-2，而您希望它们编号从 1 到 2^(H+1)-1。索引为 0 的元素不方便 - 它违反了“父 i，左子 2*i”规则，因为 0=2*0。换句话说，当我说数组中的第一个元素是根时，我的意思是树 [1]，而不是树 [0]。只需忽略树[0]。

最后，BST 的 required_array_size 高度为 H = computed_size + zero_ignoring_shift = 2^(H+1)-1 +1 = 2^(H+1)