BST минимальной высоты

Я пытаюсь решить следующую задачу: «Для отсортированного (в порядке возрастания) массива с уникальными целочисленными элементами напишите алгоритм для создания BST с минимальной высотой».

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

Обоснование, данное в книге, звучит так: «Чтобы создать дерево минимальной высоты, нам нужно как можно больше сопоставить количество узлов в левом поддереве с количеством узлов в правом поддереве. Это означает, что мы хотим, чтобы корень узел должен быть серединой массива, так как это означало бы, что половина элементов будет меньше корня, а половина больше».

Я хотел бы спросить:

  1. Почему любое дерево минимальной высоты должно быть таким, в котором количество узлов в левом поддереве максимально равно количеству узлов в правом поддереве? (Или у вас есть другой способ доказать, что лучше всего сделать корневой узел серединой массива?)

  2. Является ли дерево с минимальной высотой таким же, как сбалансированное дерево? Из предыдущего вопроса о SO у меня сложилось такое впечатление (Визуализация сбалансированного дерева), но я сбит с толку, потому что в книге конкретно указано «BST с минимальной высотой», а не «сбалансированный BST».

Спасибо.

Источник: Cracking the Coding Interview


arrays sorting binary-search-tree tree-balancing
person randomUser47534    schedule 18.05.2015    source источник

Ответы (2)


arrow_upward
0
arrow_downward

  1. Как мне нравится думать об этом, если вы балансируете дерево, используя повороты дерева (зигзагообразные и зигзагообразные вращения), вы в конечном итоге достигнете состояния, в котором левое и правое поддеревья отличаются не более чем на единицу высоты. Сбалансированное дерево не всегда должно иметь одинаковое количество дочерних элементов справа и слева; однако, если у вас есть этот инвариант (одинаковое количество детей с каждой стороны), вы можете достичь дерева, сбалансированного с помощью вращения дерева)

  2. Баланс определяется произвольно. Деревья AVL определяют его таким образом, что ни одно поддерево дерева не имеет дочерних элементов, высота которых отличается более чем на единицу. Другие деревья определяют баланс по-разному, поэтому это не одно и то же различие. Они по своей сути связаны, но не совсем одно и то же. При этом дерево минимальной высоты всегда будет сбалансировано при любом определении, поскольку балансировка существует для поддержания времени поиска BST O (log (n)) .

Если я что-то пропустил или сказал что-то не так, не стесняйтесь редактировать/исправлять меня. Надеюсь это поможет

person Andrew Malta    schedule 18.05.2015

arrow_upward
0
arrow_downward

Почему любое дерево минимальной высоты должно быть таким, в котором количество узлов в левом поддереве максимально равно количеству узлов в правом поддереве?

Может быть сценарий, когда в дереве минимальной высоты, которое, конечно, сбалансировано, может быть разное количество узлов слева и справа. Обход BST в наихудшем случае составляет O (n) в случае, если он отсортирован, а в деревьях минимальной высоты сложность для наихудшего случая составляет O (log n).

    *
   / \
  *   *
 /
*

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

Является ли дерево с минимальной высотой таким же, как сбалансированное дерево? Из предыдущего вопроса о SO у меня сложилось такое впечатление (визуализация сбалансированного дерева), но я сбит с толку, потому что в книге конкретно указано «BST с минимальной высотой», а не «сбалансированное BST».

Дерево минимальной высоты является сбалансированным, для получения более подробной информации вы можете взглянуть на деревья AVL, которые также известны как деревья со сбалансированной высотой. При создании BST сбалансированного по высоте дерева вы должны выполнять повороты (LR, RR, LL, RL).

person ashishraaj    schedule 18.05.2015