построение сбалансированного дерева

Question

Учитывая следующие отсортированные целые числа: 1 2 3 4 5 6 7 8. Как бы вы построили сбалансированное дерево поиска?

Я был бы очень признателен, если бы кто-нибудь смог объяснить без примеров кода .

Это не домашняя работа. Я делаю ревизию для экзамена.

Если приведенные выше значения помещены в сбалансированное дерево, должно ли дерево выглядеть следующим образом?

        5
      4   6
    3      7
   2        8
 1

Answer 1

Самый простой способ, вероятно, следующий:

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

Поскольку ваш список целых чисел уже отсортирован, вы можете просто выбрать значение в середине, чтобы найтисреднее значение (и нет необходимости перемещать какие-либо значения вокруг среднего значения при разбиении).Вы получаете поддеревья, просто разделяя список на две части.

Окончательное дерево зависит от того, какой узел вы выбрали в качестве среднего.Это один пример:

    4
 2     6
1 3   5 7 
          8

Answer 2

Вы можете подумать о построении снизу вверх.

У вас будет рут.Если в дереве есть только один элемент, это корень.Каждый элемент в корне будет иметь ссылку на два других узла в дереве (двоичное дерево).Один для элемента больше, чем он сам, а другой для элемента меньше, чем он сам.

Таким образом, если у вашего дерева есть только номер один, и вы собираетесь вставить номер буксировки, он будет вставлен в виде листа, а ссылка «больше чем» в корне будет указывать на узел 2.

Когда вы вставляете значение 3, вам нужно будет вставить его в ссылку «больше, чем» узла 2. Но подождите, это сделает дерево неуравновешенным, поэтому вы должны исправить это.Вам нужно будет установить узел 2 в качестве корня и указать на узел 1 в «меньше чем» и номер три в ссылке «больше чем».

Надеюсь, это поможет вам понять его немного лучше,

Окончательный результат зависит от порядка вставки элементов.Но если вы вставите как 1, 2, 3, 4, 5 ... Дерево должно быть что-то вроде:

  2
1   3

тогда

    3
  2   4
1

и после

    3
  2   4
1       5

и так далее.Пример при вставке таких узлов не очень хорош, но если вы думаете в следующем порядке: 4, 2, 6, 1, 3, 5, тогда результат должен выглядеть примерно так:

       4
  2        6
1   3    5