平衡二叉树最少节点数推导

文章目录平衡二叉树最少节点数推导一、先明确高度的含义二、最少节点树的结构特征三、为什么左边是 N(h-1)右边是 N(h-2)四、“加一层”的本质五、递推计算六、高度为 5 的树长什么样七、易错点八、结论平衡二叉树最少节点数推导平衡二叉树也就是 AVL 树要求树中每个节点的左子树高度和右子树高度之差的绝对值不超过 1。如果题目问高度为 h 的平衡二叉树最少有多少个节点关键不是去画一棵“很满”的树而是要构造一棵刚好满足平衡条件、但又尽可能少长节点的树。一、先明确高度的含义这里采用常见的定义空树高度为 0只有一个根节点时高度为 1树的高度等于从根到最远叶子节点的层数。所以高度为 1 的平衡二叉树最少有 1 个节点高度为 2 的平衡二叉树最少有 2 个节点。这两个是递推的基础。二、最少节点树的结构特征要让节点数最少同时又要让树的高度达到 h就必须让每一棵子树都“刚刚好平衡”。也就是说对于高度为 h 的树它必须有一棵高度为 h - 1 的子树用来把整体高度撑到 h另一棵子树不能太矮否则高度差会超过 1破坏平衡所以另一棵子树的最小高度只能是 h - 2同时为了让总节点数最少这两棵子树本身也必须是“最少节点平衡二叉树”。于是可以得到结构高度为 h 的最少节点平衡二叉树 一棵高度为 h - 1 的最少节点平衡二叉树 一棵高度为 h - 2 的最少节点平衡二叉树 1 个根节点。三、为什么左边是 N(h-1)右边是 N(h-2)设 N(h) 表示高度为 h 的平衡二叉树最少节点数。如果根节点的左子树高度是 h - 1右子树高度是 h - 2那么整棵树的高度就是h max ⁡ ( h − 1 , h − 2 ) 1 h − 1 1 h h \max(h-1, h-2) 1 h - 1 1 hhmax(h−1,h−2)1h−11h也就是说较高那棵子树决定了整棵树的高度。为了让节点最少左子树取高度为 h - 1 的最少节点树节点数为 N(h - 1)右子树取高度为 h - 2 的最少节点树节点数为 N(h - 2)再加上根节点 1 个。所以递推式为N ( h ) N ( h − 1 ) N ( h − 2 ) 1 N(h) N(h-1) N(h-2) 1N(h)N(h−1)N(h−2)1左、右可以互换不一定非要是左边高、右边矮。只要一棵子树高度为 h - 1另一棵为 h - 2就满足平衡条件。四、“加一层”的本质很多初学者会问为什么加上一个根节点高度就变成 h 了可以这样理解。假设我们已经有了一棵高度为 h - 1 的树一棵高度为 h - 2 的树。如果把它们分别作为某个新节点的左子树和右子树那么这个新节点就成了整棵树的根。从根出发到达最远叶子需要经过根节点这一层再加上高度为 h - 1 的子树。所以总高度是( h − 1 ) 1 h (h - 1) 1 h(h−1)1h也就是说根节点本身贡献了一层高度。五、递推计算基础情况N ( 0 ) 0 N(0) 0N(0)0N ( 1 ) 1 N(1) 1N(1)1N ( 2 ) 2 N(2) 2N(2)2继续递推高度 h递推过程最少节点数 N(h)1基础情况12基础情况23N(2) N(1) 1 2 1 144N(3) N(2) 1 4 2 175N(4) N(3) 1 7 4 1126N(5) N(4) 1 12 7 120所以高度为 5 的平衡二叉树最少有12 个节点。六、高度为 5 的树长什么样下面这棵树中左子树高度为 4右子树高度为 3满足平衡条件。第1层: 1 / \ 第2层: 2 3 / \ / \ 第3层: 4 5 6 7 / \ / \ / 第4层: 8 9 10 × 11 / \ 第5层: 12 ×其中数字表示真实节点× 表示空位置不计入节点数从 1 → 2 → 4 → 8 → 12 这条路径正好有 5 层整棵树共 12 个节点。更严谨地看根节点左子树高度为 4最少 7 个节点根节点右子树高度为 3最少 4 个节点加上根节点7 4 1 12。七、易错点平衡不等于对称平衡二叉树不要求左右子树节点数相同只要求高度差不超过 1。最少节点树往往很“偏”为了用最少的节点达到指定高度它会让一边尽量高另一边只保持最低平衡要求。不要误以为是满二叉树满二叉树或完全二叉树节点很多这里问的是“最少节点”所以要用递推而不是用 2^h - 1。高度和层数要统一理解如果题目把空树高度记为 0单节点高度记为 1那么高度为 5 对应 5 层。八、结论高度为 h 的平衡二叉树最少节点数满足N ( h ) N ( h − 1 ) N ( h − 2 ) 1 N(h) N(h-1) N(h-2) 1N(h)N(h−1)N(h−2)1其中N(h - 1) 是较高子树的最少节点数N(h - 2) 是较矮子树的最少节点数1 是新增的根节点。因此高度为 5 的平衡二叉树最少有12 个节点。