Создание сбалансированного дерева двоичного поиска

Question

Есть ли способ построить сбалансированное двоичное дерево поиска?

Пример:

1 2 3 4 5 6 7 8 9 

     5 
    /\ 
    3 etc 
    /\ 
    2 4 
/
1 

Я думаю, есть способ сделать это без использования более сложных самобалансирующехся дерев. В противном случае я могу сделать это самостоятельно, но кто-то, возможно, уже это сделал :)

---

Спасибо за ответы! Это окончательный код Python:

def _buildTree(self, keys): 
    if not keys: 
     return None 

    middle = len(keys) // 2 

    return Node(
     key=keys[middle], 
     left=self._buildTree(keys[:middle]), 
     right=self._buildTree(keys[middle + 1:]) 
     ) 

Answer 1

Для каждого поддерева:

• Найти средний элемент поддерева и положить, что в верхней части дерева.
• Найти все элементы перед средним элементом и рекурсивно использовать этот алгоритм для получения левого поддерева.
• Найдите все элементы после среднего элемента и используйте этот алгоритм рекурсивно, чтобы получить правильное поддерево.

Если вы сортируете элементы сначала (как в вашем примере), то найти средний элемент поддерева можно в постоянное время.

Это простой алгоритм построения одноразового сбалансированного дерева. Это не алгоритм для самобалансирующегося дерева.

Вот некоторые исходный код в C#, который вы можете попробовать сами:

public class Program 
{ 
    class TreeNode 
    { 
     public int Value; 
     public TreeNode Left; 
     public TreeNode Right; 
    } 

    TreeNode constructBalancedTree(List<int> values, int min, int max) 
    { 
     if (min == max) 
      return null; 

     int median = min + (max - min)/2; 
     return new TreeNode 
     { 
      Value = values[median], 
      Left = constructBalancedTree(values, min, median), 
      Right = constructBalancedTree(values, median + 1, max) 
     }; 
    } 

    TreeNode constructBalancedTree(IEnumerable<int> values) 
    { 
     return constructBalancedTree(
      values.OrderBy(x => x).ToList(), 0, values.Count()); 
    } 

    void Run() 
    { 
     TreeNode balancedTree = constructBalancedTree(Enumerable.Range(1, 9)); 
     // displayTree(balancedTree); // TODO: implement this! 
    } 

    static void Main(string[] args) 
    { 
     new Program().Run(); 
    } 
} 

Answer 2

В данной статье подробно описывается:

Дерево РЕБАЛАНСИРОВАНИЯ в оптимальном время и пространство
http://www.eecs.umich.edu/~qstout/abs/CACM86.html

Также здесь:

Одно- Балансировка дерева двоичного поиска времени: Алгоритм Day/Stout/Warren (DSW)
http://penguin.ewu.edu/~trolfe/DSWpaper/

Если вы действительно хотите это сделать «на лету», вам нужно самобалансирующееся дерево.

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

Answer 3

Сделать медиану данных (точнее, ближайший элемент в массиве к медиане) корень из дерево. И так рекурсивно.