сбалансированное бинарное дерево поиска с использованием sortedset

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

Редактировать добавленный код из комментариев

да, это домашнее задание... и вот что я получил в виде кода:

using System; 
namespace bst { 
    public class Node { 
        public int value; 
        public Node Right = null; 
        public Node Left = null; 

        public Node(int value) 
        { 
            this.value = value; 
        } 
    } 

    public class BST { 
        public Node Root = null; 
        public BST() { }

        public void Add(int new_value) 
        { 
            if(Search(new_value)) 
            {
                Console.WriteLine("value (" + new_value + ") already");
            }
            else
            {
                AddNode(this.Root,new_value);
            }
        }
    }
}

c# binary-tree binary-search-tree
person Sam Omar    schedule 20.01.2011    source источник

Ответы (2)


arrow_upward
2
arrow_downward

Используйте рекурсию. Каждая ветвь генерирует новую ветвь, выберите средний элемент в несортированном наборе, медиану. Поместите его в текущий элемент дерева. Скопируйте все элементы меньше медианы в другой массив, отправьте этот новый массив на вызов того же метода. Скопируйте все элементы, превышающие медиану, в другой массив, отправьте этот новый массив на вызов того же метода.\

Сбалансированные деревья должны иметь нечетное количество элементов, если только основной родительский узел не заполнен. Вам нужно решить, есть ли два значения, которые являются медианой, принадлежит ли дубликат к нижней или верхней ветви. В моем примере я поставил дубликаты на верхнюю ветку.

Медиана будет числом, где равное количество чисел меньше и больше числа. 1,2,3,3,4,18,29,105,123 В этом случае медиана равна 4, хотя среднее (или среднее) намного выше.

Я не включил код, определяющий медиану.

BuildTreeItem(TreeItem Item, Array Set)  
{
  Array Smalls;
  Array Larges;
  Median = DetermineMedian(Set);
  Item.Value = Median;
  if(Set.Count() == 1)
    return;  
  for (int i = 0; int i < Set.Count(); i++)
  {
    if(Set[i] < Median)
    {
      Smalls.new(Set[i]);
    }
    else
    {
      Larges.new(Set[i]);
    }
  }
  Item.Lower = new TreeItem;
  Item.Upper = new TreeItem;
  BuildTreeItem(TreeItem.Lower, Smalls);
  BuildTreeItem(TreeItem.Upper, Larges);
}
person Lee Louviere    schedule 21.01.2011
comment
поэтому все, что мне нужно, это просто добавить код для медианы, и это сгенерирует дерево. - person Sam Omar; 21.01.2011

arrow_upward
0
arrow_downward

Если это не домашнее задание, самым простым решением будет сначала отсортировать данные, а затем построить дерево, используя средний элемент в качестве корня и спускаясь вниз по каждой половине. Метод, предложенный Xaade, похож на , но намного медленнее из-за сложности DefinitionMedian.

Другой вариант — рассмотреть алгоритмы построения сбалансированных деревьев (например, http://en.wikipedia.org/wiki/Red-black_tree ), чтобы узнать, соответствует ли он вашим требованиям.

РЕДАКТИРОВАТЬ: удаление неверного утверждения о скорости алгоритма Xaade - на самом деле это так же быстро, как быстрая сортировка (n log n - проверять каждый элемент на каждом уровне рекурсии с log n уровней рекурсии), не знаю, почему я оценил это медленнее.

person Alexei Levenkov    schedule 21.01.2011
comment
с помощью системы; пространство имен bst ​​{ общедоступный класс Node { public int value; право публичного узла = ноль; общедоступный узел слева = ноль; общедоступный узел (целое значение) { this.value = значение; } } открытый класс BST { открытый корень узла = ноль; общественный BST () { } - person Sam Omar; 21.01.2011
comment
public void Add(int new_value) { if(Search(new_value)) { Console.WriteLine(value ( + new_value + ) уже); } else { AddNode(this.Root,new_value); } } - person Sam Omar; 21.01.2011
comment
в основном я полностью потерялся, это проблема с домашней работой, но сначала мне нужно определить, как заставить это дерево работать над моей домашней работой, и начать экономить время и работать над функциями поиска, но я просто поражен, было бы здорово, если бы я получить помощь для части кодирования... - person Sam Omar; 21.01.2011
comment
Зависит от метода сортировки. Пузырьковая сортировка будет медленнее моего алгоритма. Хотя быстрая сортировка была бы быстрее - person Lee Louviere; 21.01.2011
comment
Пока что я не могу найти метод рекурсивного выбора медиан, который был бы быстрее, чем простая сортировка набора для начала. - person Lee Louviere; 26.01.2011
comment
Интересно, поскольку мы знаем, что это будет бинарное дерево. Не проще ли построить дерево и добавить указатели на узлы в массив, а затем отсортировать исходный массив в массив указателей. - person Lee Louviere; 26.01.2011