关于二叉搜索树的问题 [英] questions about binary search tree
问题描述
证明每个n节点二叉搜索树的可能性均不相同(假设以随机顺序插入项目)，并且平衡树比直线树更有可能.
Show that every n-node binary search tree is not equally likely (assuming items are inserted in random order), and that balanced trees are more probable than straight-line trees.
它是如何证明数学的?
推荐答案
Number of ways to get a single line, most imbalanced, deepest tree with n nodes: 2^(n-1) Explanation: 2 ways to pick up first node (greatest or smallest) X 2 ways to pick up second node (greatest or smallest among the n-1 remaining nodes ... X 2 ways to pick up the (n-1)th node X 1 way to pick up the last node
以平衡的方式将n项添加到二叉树的方式数量: 令g(n，m)表示通过一次从一个列表或另一个列表中选取元素直到两个列表都为空来合并两个有序列表的方式的数量. g(n，m)= g(n-1，m)+ g(n，m-1)碰巧对应于Pascal Triangle中定义的数字.这将使n + m选择n或n + m选择m =(n + m)！/n！ (n + m-n)！ =(n + m)！/(n！m！) 例子: 合并两个包含2个元素的有序列表的方式数量= 4！/(2！2！)= 24/4 = 6 假设两个列表如下:
Number of ways to add n items to a binary tree in such a way that it is balanced: Let g(n,m) denote the number of ways to merge two ordered lists by picking elements from one list or the other one at a time until both lists are empty. g(n,m) = g(n-1,m) + g(n,m-1) which happen to correspond to the numbers defined in the Pascal Triangle. That would give n+m chose n or n+m chose m = (n+m)! / n! (n+m-n)! = (n+m)!/(n! m!) Example: Number of ways to merge two ordered lists containing 2 elements each = 4!/(2! 2!) = 24 / 4 = 6 Assuming the two lists are as follows:
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个排序元素添加到空的二叉树中以使二叉树达到平衡的组合数.达到此目的的唯一方法是先添加
Now, let f(n) denote the number of combinations in which n sorted elements can be added to a empty binary tree such that the binary tree is balanced. The only way to achieve that is to first add
- 如果n为奇数，则为中间元素.那将是元素上限(n/2).每边将具有n/2-1个元素.
- 如果n为偶数，则元素n/2或元素n/2 + 1.一侧将具有n/2-1个元素，另一侧将具有n/2个元素，反之亦然.
一旦选择了中间元素，则左侧的所有元素将始终位于左侧子树上，而右侧的所有元素将始终位于右侧子树上.假设右侧的元素以平衡左子树的方式排序，并且右侧的元素也以平衡右子树的方式排序，以任何方式合并两个列表将始终导致子树是平衡的.这意味着对于分别落在左右子树上的n和m个元素的每个列表，以使两个子树保持平衡，存在(n + m)！/(n！m！)合并它们，以实现结果相同.
Once the middle element is selected, all elements to the left will always fall on the left subtree and all elements on the right will always fall on the right subtree. Assuming the elements on the right are ordered in such a way that the left subtree is balanced and the elements on the right are also ordered in such a way that the right subtree is balanced, merging the two lists in any way will always result in both subtree being balanced. That means that for each list of n and m elements that respectively fall on the left and right subtree such that both subtrees are balanced, there are (n+m)!/(n!m!) to merge them so as to achieve the same result.
那会给我们(n + m)！/(n！m！)x f(n)x f(m)
That would give us (n+m)!/(n!m!) x f(n) x f(m)
我们现在可以将其表述如下: 基本案例:
We can now formulate this as follows: Base cases:
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总是得到一个整数，并且会形成一个完全平衡的树).
Rest to transform this into a non recursive formula in terms of n. Maybe it would be easier to start with the easiest case where n = 2^m - 1 (i.e. removing a node and dividing by two will always give a whole number and will result in a completely balanced tree).
Note: I posted a related math question here: https://math.stackexchange.com/questions/460767/recurrent-relation-for-number-of-ways-to-get-a-balanced-n-binary-tree
以下是一个C#控制台应用程序，该应用程序列出了可将节点添加到二叉树以使其平衡的所有序列(运行
Following is a C# console application that lists all the sequences in which nodes can be added to a binary tree so as to have it balanced (Run it here ):
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;
}
}
}
}
}
这篇关于关于二叉搜索树的问题的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
