вопросы о двоичном дереве поиска

Question

Покажите, что каждое дерево двоичного поиска n-узла неравновероятно (при условии, что элементы вставлены в случайном порядке), и что сбалансированные деревья более вероятны, чем прямые деревья.

Как это доказать математику?

Answer 1

Количество возможных конфигураций дерева: см With ' N ' no of nodes, how many different Binary and Binary Search Trees possible?

Количество способов получить одну строку, наиболее несбалансированной, глубочайшей дерево с п узлами: 2^(п-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 + 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 

пусть теперь п (п) обозначат число комбинаций, в которых п отсортированных элементы могут быть добавлены в пустое двоичное дерево так что бинарное дерево сбалансировано. Единственный способ добиться этого - сначала добавить

• средний элемент, если n нечетно. Это будет элементный потолок (n/2). Каждая сторона имела бы n/2-1 элементов.
• любой элемент n/2 или элемент n/2 + 1, если n четный. Одна сторона имела бы элемент n/2-1, другую сторону n/2 элементов и наоборот.

После выбора среднего элемента все элементы слева всегда будут лежать на левом поддереве, и все элементы справа всегда будут падать на правое поддерево. Предполагая, что элементы справа упорядочены таким образом, что левое поддерево сбалансировано, а элементы справа также упорядочены таким образом, что правильное поддерево сбалансировано, объединение обоих списков каким-либо образом всегда приведет к поддерево сбалансировано. Это означает, что для каждого списка из n и m элементов, которые соответственно попадают в левое и правое поддерево, так что обе поддеревья сбалансированы, есть (n + m)!/(N! M!), Чтобы объединить их, чтобы достичь такой же результат.

Это даст нам (n + m)!/(N! M!) XF (п) XF (м)

Теперь мы можем сформулировать это следующим образом: Базовые случаи:

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 (т. Е. Удаление узла и деление на два всегда даст целое число и приведет к полностью сбалансированному дереву).

Примечание: Я отправил соответствующий математический вопрос здесь: https://math.stackexchange.com/questions/460767/recurrent-relation-for-number-of-ways-to-get-a-balanced-n-binary-tree

Ниже в C# консольное приложение, в котором перечислены все последовательности, в которой узлы могут быть добавлены в бинарное дерево так, чтобы он сбалансирован (Выполнить это 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; 
       } 

      } 
     } 
    } 
} 

Answer 2

Каждый н-узел бинарное дерево поиска не одинаково вероятно потому, что, если элементы будут вставлены в произвольном порядке, существует гораздо больше вероятность того, что вход не будет в строго порядке возрастания или убывания. Пока элементы не находятся в порядке возрастания или убывания, прямолинейное дерево невозможно. Например, в дереве из четырех записей с ключами 1, 2, 3 и 4 есть 4! или 24 способа для заказа этих элементов в качестве входных данных. Только два из этих способов могут привести к прямолинейному дереву (4, 3, 2, 1 и 1, 2, 3, 4). В этом случае вероятность линейного дерева составляет приблизительно 8,3%, тогда как вероятность (несколько) сбалансированного дерева составляет 91,6%. Ясно, что шансы против шансов получить прямолинейное дерево для результата.