Как строятся большие двоичные деревья?

Question

Это вопрос, который беспокоил меня годами. Я хочу знать, как строятся большие двоичные деревья, единственный метод, который я знаю, - это создать функцию, чтобы нажимать один элемент на дерево (функция, называемая insert();). Если у меня есть 3 элемента дерева и вы хотите добавить 5 элементов, мне придется вызвать функцию insert 5 раз. Это кажется довольно плохим методом, что, если я хочу добавить 50 элементов? Должен быть лучший способ, чем просто вызвать функцию insert() пятьдесят раз.

Answer 1

Существует. Кнут дает алгоритм построения разумно сбалансированного двоичного кода от отсортированный ввод, в ACP том III Я думаю.

Answer 2

Если данные предварительно отсортированы, вы можете построить их рекурсивно.

В принципе, чтобы построить дерево для некоторых входных сигналов:

1. Создать новый узел
2. Если вход только один вход, значение узла является то, что запись
3. В противном случае:
   1. В левом поддереве узла поместите дерево, построенное из первой половины ввода
   2. В правом поддереве узла поместите дерево, построенное из м во второй половине входного

Третий шаг будет рекурсивно применить себя к частям ввода.

Вот некоторые псевдо-код:

FUNCTION TREE (input -> node) 
    IF input IS 1 ENTRY 
     VALUE OF node IS entry OF input 
    ELSE 
     SPLIT input IN 2 
     LEFT SUB-TREE OF node IS TREE(FIRST HALF OF input) 
     RIGHT SUB-TREE OF node IS TREE(SECOND HALF OF input) 

Вот некоторые LINQPad C# код вы можете экспериментировать с:

// Add the following two using-directives to LINQPad: 
// System.Drawing 
// System.Drawing.Imaging 

static Bitmap _Dummy = new Bitmap(16, 16, PixelFormat.Format24bppRgb); 
static Font _Font = new Font("Arial", 12); 

void Main() 
{ 
    var sorted = Enumerable.Range(1, 16).ToArray(); 
    var tree = BuildTree(sorted); 
    Visualize(tree); 
} 

public Node<T> BuildTree<T>(T[] input) 
{ 
    return BuildTree<T>(input, 0, input.Length); 
} 

public Node<T> BuildTree<T>(T[] input, int left, int right) 
{ 
    if (right <= left) 
     return null; 

    if (right == left + 1) 
     return new Node<T> { Value = input[left] }; 

    int middle = (left + right)/2; 
    return new Node<T> 
    { 
     Left = BuildTree<T>(input, left, middle), 
     Right = BuildTree<T>(input, middle, right) 
    }; 
} 

public class Node<T> 
{ 
    public T Value; 
    public Node<T> Left; 
    public Node<T> Right; 

    public Bitmap ToBitmap() 
    { 
     Size valueSize; 
     using (Graphics g = Graphics.FromImage(_Dummy)) 
     { 
      var tempSize = g.MeasureString(Value.ToString(), _Font); 
      valueSize = new Size((int)tempSize.Width + 4, (int)tempSize.Height + 4); 
     } 

     Bitmap bitmap; 
     Color valueColor = Color.LightPink; 
     if (Left == null && Right == null) 
     { 
      bitmap = new Bitmap(valueSize.Width, valueSize.Height); 
      using (var g = Graphics.FromImage(bitmap)) 
       g.Clear(Color.White); 
      valueColor = Color.LightGreen; 
     } 
     else 
     { 
      using (var leftBitmap = Left.ToBitmap()) 
      using (var rightBitmap = Right.ToBitmap()) 
      { 
       int subNodeHeight = Math.Max(leftBitmap.Height, rightBitmap.Height); 
       bitmap = new Bitmap(
        leftBitmap.Width + rightBitmap.Width + valueSize.Width, 
        valueSize.Height + 32 + subNodeHeight); 

       using (var g = Graphics.FromImage(bitmap)) 
       { 
        g.Clear(Color.White); 
        int baseY = valueSize.Height + 32; 

        int leftTop = baseY; // + (subNodeHeight - leftBitmap.Height)/2; 
        g.DrawImage(leftBitmap, 0, leftTop); 

        int rightTop = baseY; // + (subNodeHeight - rightBitmap.Height)/2; 
        g.DrawImage(rightBitmap, bitmap.Width - rightBitmap.Width, rightTop); 

        g.DrawLine(Pens.Black, bitmap.Width/2 - 4, valueSize.Height, leftBitmap.Width/2, leftTop); 
        g.DrawLine(Pens.Black, bitmap.Width/2 + 4, valueSize.Height, bitmap.Width - rightBitmap.Width/2, rightTop); 
       } 
      } 
     } 

     using (var g = Graphics.FromImage(bitmap)) 
     { 
      float x = (bitmap.Width - valueSize.Width)/2; 
      using (var b = new SolidBrush(valueColor)) 
       g.FillRectangle(b, x, 0, valueSize.Width - 1, valueSize.Height - 1); 
      g.DrawRectangle(Pens.Black, x, 0, valueSize.Width - 1, valueSize.Height - 1); 
      if (Left == null && Right == null) 
       g.DrawString(Value.ToString(), _Font, Brushes.Black, x + 1, 2); 
     } 

     return bitmap; 
    } 
} 

void Visualize<T>(Node<T> node) 
{ 
    node.ToBitmap().Dump(); 
} 

Вот результат: