сбалансированное двоичное дерево поиска с использованием sortedset - PullRequest
Новая
       9

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

0 голосов
/ 21 января 2011

Помогите, пожалуйста, я пытался сгенерировать случайное двоичное дерево поиска размером 1024, и элементы должны быть случайным sortedset ... Я могу написать код для создания двоичного дерева поиска вручную, добавляя элементы вручнуюно я не могу написать код, который будет генерировать случайное сбалансированное двоичное дерево размером 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);
            }
        }
    }
}

Ответы [ 2 ]

2 голосов
/ 21 января 2011

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

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

Медиана будет числом, в котором равное количество чисел меньше и больше числа.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);
}
0 голосов
/ 21 января 2011

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

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

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

...