Ожидаемая высота произвольно заполненного бинарного дерева поиска по n различным ключам составляет O (log (n))

Question

Я работаю над проектом для школы, и у нас есть задание:

1. Реализация операции вставки дерева (T, z) в двоичное дерево поиска.
2. Повторно вставьте n случайно выбранных чисел в двоичное дерево поиска и соберите высоту ч.
3. Постройте на этом же графике количество ч / lg (n) против n.

У меня есть законченная программа, которая выводит значение n из 250-50K, среднюю высоту моего случайно заполненного BST и значение высота (n) / log ₂ (n). Я могу предоставить код, если необходимо, но псевдокод для программы выглядит так:

collectData()
for n = 250 to 10,000 by 250 // 250, 500, 750, …. 10,000
    sum_heightn = 0
    for j = 1 to 10 do //Take 10 measurements mj for j=1 to 10
        for i = 1 to n
           pick randomly a number p in the range [0,n]
           create a node z
           set z.key = p
           Tree-Insert(T,z)
        Measure the height hj of the tree
        Discard Tree
        sum_height += hj
collect Height(n)= sum_heightn/10 // Average height for n
Write in a file F the value n and Height(n)/log_2(n).  

Iя изо всех сил пытаюсь понять, что означает значение, которое я получаю при расчете h (n) / log ₂ (n) .Может кто-нибудь помочь объяснить?Спасибо.

Answer 1

Двоичное дерево высотой h может иметь не более 2^h - 1 узлов.

     1
    / \
   /   \
  2     3

Высота дерева выше 2 и максимальное количество узлов, которое вы можете иметьв этом дереве 2^2 - 1 = 3.

log_2(n) для большого n обозначает (приблизительно) высоту полностью заполненного дерева.Точно так же вы можете сказать, что асимптотически высота сбалансированного дерева с n узлами будет O(log_2(n)).

height / log_2(n) - это просто отношение, которое может пойти

• максимум до n / log_2(n), когда дерево перекошено (когда порядок вставки либо увеличивается, либо уменьшается).
• минимум до 1, когда дерево идеально сбалансировано и высота дерева становитсяlog_2(n).

Вы можете увидеть это соотношение следующим образом: оно отображает степень асимметрии данного дерева.Если этот рацион близок к n/log_2(n), то дерево очень перекошено, а если отношение достаточно близко к 1, то дерево сбалансировано much.