线段树节点个数的递推公式与通项公式

2024-07-05 08:14| 来源: 网络整理| 查看: 265

不用二叉堆而是用含有指针域的节点构造线段树的话，其所需节点个数与区间长度N的关系是什么呢？

递推公式

记f(x)表示根节点区间长度为x的线段树的节点个数，那么有：

/ 2f(x/2) + 1, 当x>1且x为偶数时； f(x) = | f((x+1)/2) + f((x-1)/2) + 1, 当x>1且x为奇数时； \ 1, 当x=1时。

这条递推公式与区间划分的递归步骤有相似之处。

通项公式

前4项的结果

x 1 2 3 4 ... f(x) 1 3 5 7 ...

猜测：

f(x) = 2x - 1

神奇，原先的递推公式描述的竟然是奇数！

证明：

定理：“对任何一棵二叉树T，如果其终端结点数为n0，度为2的结点数为n2，则n0=n2+1。”

由于线段树对区间作划分时总是分割成左右两个子区间，因此线段树里只有度为0和度为2的节点。而最终是分割至区间长度为1的叶子节点，因此所有叶子节点个数之和为根节点区间N。 n0 = N; n2 = n0 - 1; 总节点个数= n0 + n2 = 2N - 1；

原来如此。

定理n0=n2+1的证明

设二叉树总节点数目为N，有

N=N0+N1+N2——(公式1) 二叉树度数总和为 0*N0+1*N1+2*N2；而由二叉树的图形可以看出除根节点外，每个结点上方对应着一个度（为更形象，可以理解成结点自己的头上有一根“绳子”挂着自己）（可验证当仅有根节点时也满足这个规律），所以结点总数比度数多1，则有

N=N1+2*+1——(公式2) 公式1代入公式2即可得出：

N0=N2+1

【本文地址】

公司简介

联系我们