すべての n ノードの二分探索木の可能性が等しくないこと (項目がランダムな順序で挿入されると仮定)、およびバランスの取れた木は直線的な木よりも可能性が高いことを示します。
それはどのように数学的に証明されますか?
1595 次
2 に答える
4
可能なツリー構成の数:ノード数が ' N ' の場合、異なる二分木および二分探索木はいくつ可能か?を参照してください。
n 個のノードを持つ単一の行、最も不均衡な、最も深いツリーを取得する方法の数: 2^(n-1) 説明: 最初のノード (最大または最小) を取得する 2 つの方法 X 2 番目のノード (最大または最小)を取得する 2 つの方法残りの n-1 ノードの中で最小 ... (n-1) 番目のノードをピックアップする X 2 つの方法 X 最後のノードをピックアップする 1 つの方法
バランスがとれるように二分木に n 個の項目を追加する方法の数: g(n,m) が、2 つの順序付けられたリストをマージする方法の数を示します。両方のリストが空になるまで。g(n,m) = g(n-1,m) + g(n,m-1) これはたまたまパスカル三角形で定義された数に対応しています。これにより、n+m が選択された n または n+m が選択された m = (n+m) が得られます。/ン！(n+mn)! = (n+m)!/(n! m!) 例: それぞれ 2 つの要素を含む 2 つの順序付きリストをマージする方法の数 = 4!/(2! 2!) = 24 / 4 = 6 2 つのリストが次のとおりです。
1 A
2 B
6 つのマージの組み合わせは次のとおりです。
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 要素があり、その逆も同様です。
中央の要素が選択されると、左側のすべての要素は常に左側のサブツリーに配置され、右側のすべての要素は常に右側のサブツリーに配置されます。右側の要素が左側のサブツリーのバランスがとれるように並べられ、右側の要素も右側のサブツリーのバランスがとれるように並べられていると仮定すると、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 つのレコードのツリーでは、4! または、これらのアイテムを入力として注文するための 24 の方法。これらの方法のうち、直線ツリーになるのは 2 つだけです (4、3、2、1 および 1、2、3、4)。この場合、直線ツリーの確率は約 8.3% ですが、(やや) バランスの取れたツリーの確率は 91.6% です。明らかに、オッズは、結果に対して直線ツリーが得られる可能性に反しています。
于 2016-08-28T13:03:53.043 に答える