证明每个 n 节点二叉搜索树的可能性不均等（假设项目以随机顺序插入），并且平衡树比直线树更有可能。
它是如何证明数学的？
问问题
1595 次
2 回答
4
可能的树配置数量：请参阅“N”个节点，可能有多少种不同的二叉搜索树和二叉搜索树？
获得具有 n 个节点的单行、最不平衡、最深的树的方法数：2^(n-1) 解释：获取第一个节点（最大或最小）的 2 种方法 X 获取第二个节点（最大或最小）的 2 种方法n-1 个剩余节点中最小的... X 2 种方式来获取第 (n-1) 个节点 X 1 方式来获取最后一个节点
以平衡的方式将 n 项添加到二叉树的方法数： 让 g(n,m) 表示通过一次从一个列表或另一个列表中选择元素来合并两个有序列表的方法数直到两个列表都为空。g(n,m) = g(n-1,m) + g(n,m-1) 这恰好对应于帕斯卡三角形中定义的数字。这将使 n+m 选择 n 或 n+m 选择 m = (n+m)！/n！(n+mn)！= (n+m)!/(n!m!) 示例：合并两个包含 2 个元素的有序列表的方法数 = 4!/(2!2!) = 24 / 4 = 6 假设两个列表为如下：
1 A
2 B
六种合并组合是：
1 1 1 A A A
2 A A B 1 1
A 2 B 1 B 2
B B 2 2 2 B
现在，让 f(n) 表示可以将 n 个已排序元素添加到空二叉树以使二叉树平衡的组合数。实现这一目标的唯一方法是首先添加
- 如果 n 是奇数，则为中间元素。那将是元素上限（n / 2）。每边都有 n/2-1 个元素。
- 如果 n 是偶数，则为元素 n/2 或元素 n/2+1。一侧有 n/2-1 个元素，另一侧有 n/2 个元素，反之亦然。
一旦选择了中间元素，左侧的所有元素将始终落在左子树上，而右侧的所有元素将始终落在右子树上。假设右边的元素以左子树平衡的方式排序，而右边的元素也以右子树平衡的方式排序，以任何方式合并两个列表总是会导致两者子树是平衡的。这意味着对于每个分别落在左右子树上的 n 和 m 个元素的列表，使得两个子树都是平衡的，有 (n+m)!/(n!m!) 将它们合并以实现同样的结果。
这会给我们 (n+m)!/(n!m!) xf(n) xf(m)
我们现在可以将其表述如下： 基本情况：
f(1) = 1
f(2) = 2
一般情况：
f(n) = (n-1)!/[((n-1)/2)!]^2 x [f((n-1)/2)]^2 | n odd
f(n) = (n-1)!/((n/2-1)! x (n/2)!) x 2 x f(n/2-1) x f(n/2) | n even
休息以将其转换为根据 n 的非递归公式。也许从 n = 2^m - 1 的最简单情况开始会更容易（即删除一个节点并除以 2 将始终给出一个整数，并会产生一个完全平衡的树）。
注意：我在这里发布了一个相关的数学问题：https ://math.stackexchange.com/questions/460767/recurrent-relation-for-number-of-ways-to-get-a-balanced-n-binary-tree
以下是一个 C# 控制台应用程序，它列出了可以将节点添加到二叉树以使其平衡的所有序列（在此处运行）：
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace AllBalancedTrees
{
class Program
{
static void Main(string[] args)
{
char[] nodes = { 'A', 'B', 'C', 'D', 'E' };
AllBalancedTrees<char> AllBalancedTrees = new AllBalancedTrees<char>();
foreach (char[] a in AllBalancedTrees.allBalancedTreeCombinations(nodes))
{
foreach (char c in a)
{
Console.Write(c + " ");
}
Console.WriteLine();
}
Console.ReadKey();
}
}
class AllBalancedTrees<T>
{
public IEnumerable<T[]> allBalancedTreeCombinations(T[] nodes)
{
T[] result;
if (nodes.Length == 1)
{
yield return nodes;
}
else if (nodes.Length == 2)
{
yield return nodes;
T[] nodes2 = new T[2];
nodes2[0] = nodes[1];
nodes2[1] = nodes[0];
yield return nodes2;
}
else if (nodes.Length % 2 == 1)
{
int mid = (nodes.Length - 1) / 2;
T[] left = new T[mid];
T[] right = new T[mid];
Array.Copy(nodes, 0, left, 0, mid);
Array.Copy(nodes, mid + 1, right, 0, mid);
foreach (T[] l in allBalancedTreeCombinations(left))
{
foreach (T[] r in allBalancedTreeCombinations(right))
{
result = new T[nodes.Length];
result[0] = nodes[mid];
foreach (T[] a in allMergeCombinations(l, r))
{
Array.Copy(a, 0, result, 1, a.Length);
yield return result;
}
}
}
}
else
{
int mid = (nodes.Length) / 2;
T[] left = new T[mid];
T[] right = new T[mid - 1];
Array.Copy(nodes, 0, left, 0, mid);
Array.Copy(nodes, mid + 1, right, 0, mid - 1);
foreach (T[] l in allBalancedTreeCombinations(left))
{
foreach (T[] r in allBalancedTreeCombinations(right))
{
result = new T[nodes.Length];
result[0] = nodes[mid];
foreach (T[] a in allMergeCombinations(l, r))
{
Array.Copy(a, 0, result, 1, a.Length);
yield return result;
}
}
}
mid = nodes.Length / 2 - 1;
left = new T[mid];
right = new T[mid + 1];
Array.Copy(nodes, 0, left, 0, mid);
Array.Copy(nodes, mid + 1, right, 0, mid+1);
foreach (T[] l in allBalancedTreeCombinations(left))
{
foreach (T[] r in allBalancedTreeCombinations(right))
{
result = new T[nodes.Length];
result[0] = nodes[mid];
foreach (T[] a in allMergeCombinations(l, r))
{
Array.Copy(a, 0, result, 1, a.Length);
yield return result;
}
}
}
}
}
public IEnumerable<T[]> allMergeCombinations(T[] firstArray, T[] secondArray)
{
if (firstArray.Length == 0)
{
yield return secondArray;
}
else if (secondArray.Length == 0)
{
yield return firstArray;
}
else
{
T[] result;
T[] firstMinusOne;
firstMinusOne = new T[firstArray.Length - 1];
Array.Copy(firstArray, 1, firstMinusOne, 0, firstMinusOne.Length);
foreach (T[] a in allMergeCombinations(firstMinusOne, secondArray))
{
result = new T[firstArray.Length + secondArray.Length];
result[0] = firstArray[0];
Array.Copy(a, 0, result, 1, a.Length);
yield return result;
}
T[] secondMinusOne;
secondMinusOne = new T[secondArray.Length - 1];
Array.Copy(secondArray, 1, secondMinusOne, 0, secondMinusOne.Length);
foreach (T[] a in allMergeCombinations(firstArray, secondMinusOne))
{
result = new T[firstArray.Length + secondArray.Length];
result[0] = secondArray[0];
Array.Copy(a, 0, result, 1, a.Length);
yield return result;
}
}
}
}
}
于 2013-08-04T19:12:33.413 回答
0
每个 n 节点二叉搜索树的可能性不均等，因为如果项目以随机顺序插入，则输入不会严格按递增或递减顺序的可能性要大得多。只要项目不是升序或降序，直线树是不可能的。例如，在键为 1、2、3 和 4 的四个记录的树中，有 4 个！或 24 种方式将这些项目作为输入进行排序。这些方法中只有两种可以生成直线树（4、3、2、1 和 1、2、3、4）。在这种情况下，直线树的概率约为 8.3%，而（有些）平衡树的概率为 91.6%。显然，几率与获得结果的直线树的机会相反。
于 2016-08-28T13:03:53.043 回答