您的位置: 首页 > 文章 > Algorithm 3: Complete binary tree

Algorithm 3: Complete binary tree

分类: 文章 • 2025-01-15 11:33:52

完全二叉树及其性质(可用于heapsort等)

如下图所示，是一棵近似的完全二叉树，以此举例说明。(b)是该树用数组的存储的表示形式，其中数组中的连线部分，代表着后面被连线的元素是前一个元素的孩子节点。

下面描述，如何通过完全二叉树的相关性质对于数组中位置下标为 idx 的元素，快速找到其孩子节点的元素在数组中的下表位置ci1,ci2

Algorithm 3: Complete binary tree

完全二叉树的节点总数为 2(n−1)−1 个。
$设 k 为完全二叉树的第 k 层 (从第 0 层起) ， n o d e k = 2 k$
$n 为完全二叉树的总层数，则 : N o d e s N u m = \sum k = 0 n 2 k$
$N o d e s N u m = \sum k = 0 n 2 k = 1 + 21 + 22 + . . . + 2 n$
根据公式:

$∴ N o d e s N u m = 2 n + 1 - 1 2 - 1 = 2 n + 1 - 1$

Algorithm 3: Complete binary tree

2. 因此，当我们想求得数组中下标为idx 的孩子节点的位置，其计算方式如下：

求 得 i d x 元 素 的 上 面 一 层 的 层 数 值 w : 有 不 等 式 成 立 : 2 w + 1 - 1 < i d x

2 w + 1 - 1 即 为 前 w 层 的 (包 括 第 w 层) 的 节 点 总 数 ， 数 量 即 对 应 着 编 号

w = ⌈ l o g 2 (i d x + 1) - 1 ⌉ - 1

求 得 i d x 所 对 应 的 上 一 层 层 数 w 后 ， 就 可 以 算 得 i d x 节 点 所 在 曾 有 多 少 个 节 点 在 i d x 节 点 前 面 ：

s = i d x - (2 w + 1 - 1 + 1) = i d x 节 点 层 在 i d x 节 点 前 面 的 元 素 个 数 。 (2 w + 1 - 1 + 1) 为 i d x 层 第 一 个 元 素 的 下 标 编 号

∴ c i 1 = (2 w + 1 + 1 - 1 + 1) + 2 s, c i 2 = c i 1 + 1

2w+1+1−1+1)为idx节点所在层的最大编号+1，即idx的下一层(孩子节点所在层)的第一个元素的下标编号。2s为在idx节点的第一个孩子节点之前有多少个节点。

举例说明: 如求得节点3的孩子节点的下标编号
- 求得3节点的上一层w=⌈log2(3+1)−1⌉−1=0
- 求得3号节点所在层在3号节点之前的元素个数：3−2(w+1)−1+1=1。
- 求得3号节点孩子节点所在层的第一个元素的编号:2w+1+1+1=4
- 求得ci1=4+21=6,ci2=7