Выбранный вами метод состоит в том, чтобы построить дерево в обратном направлении: снизу вверх, справа налево; начиная с последнего элемента вашего списка. Это делает вашу buildBPT функцию красивой, но требует, чтобы ваша insertElement была слишком сложной. Чтобы построить двоичное дерево таким способом, как в ширину, потребуется несколько сложных поворотов на каждом шаге после первых трех.
Добавление 8 узлов в дерево потребует следующих шагов (смотрите, как вставляются узлы). от последнего к первому):
. 4
6 6
8 7 8 . .
. .
3
7 4 5
8 . 6 7 8 .
6 2
7 8 3 4
5 6 7 8
5
6 7 1
8 . . . 2 3
4 5 6 7
8 . . . . . . .
Если вместо этого вы вставите узлы слева направо, сверху вниз, вы получите гораздо более простое решение, не требующее поворота, а вместо этого некоторая древовидная структура. Смотрите порядок вставки; всегда существующие значения остаются там, где они были:
. 1
2 3
1 4 5 . .
. .
1
1 2 3
2 . 4 5 6 .
1 1
2 3 2 3
4 5 6 7
1
2 3 1
4 . . . 2 3
4 5 6 7
8 . . . . . . .
Шаг вставки имеет асимптотику c сложность времени порядка O(n^2), где n - количество узлов для вставки , поскольку вы вставляете узлы один за другим, а затем перебираете узлы, уже присутствующие в дереве.
Когда мы вставляем слева направо, хитрость заключается в проверке того, находится ли левое поддерево завершено:
- , если это так, и правое поддерево не завершено, затем вернитесь вправо.
- , если оно есть, и правое поддерево также завершите, затем повторите влево (начиная с новой строки).
- , если это не так, затем выполните возврат влево.
Вот мой (более обобщенный c) решение:
data Tree a = Leaf | Node a (Tree a) (Tree a)
deriving (Eq, Show)
main = do
let l1 = ["A1-Gate", "North-Region", "South-Region", "Convention Center",
"Rectorate", "Academic Building1", "Academic Building2"]
let l2 = [0.0, 0.5, 0.7, 0.3, 0.6, 1.2, 1.4, 1.2]
print $ treeFromList $ zip l1 l2
mkNode :: a -> Tree a
mkNode x = Node x Leaf Leaf
insertValue :: Tree a -> a -> Tree a
insertValue Leaf y = mkNode y
insertValue (Node x left right) y
| isComplete left && nodeCount left /= nodeCount right = Node x left (insertValue right y)
| otherwise = Node x (insertValue left y) right
where nodeCount Leaf = 0
nodeCount (Node _ left right) = 1 + nodeCount left + nodeCount right
depth Leaf = 0
depth (Node _ left right) = 1 + max (depth left) (depth right)
isComplete n = nodeCount n == 2 ^ (depth n) - 1
treeFromList :: (Show a) => [a] -> Tree a
treeFromList = foldl insertValue Leaf
РЕДАКТИРОВАТЬ: более подробное объяснение:
Идея состоит в том, чтобы запомнить, в каком порядке вы вставляете узлы: слева направо * Сначала 1033 *, затем сверху вниз . Я сжал различные случаи в фактической функции, но вы можете расширить их до трех:
- Левая сторона завершена? Если нет, то вставьте в левую сторону.
- Является ли правая сторона такой же полной, как левая, которая завершена? Если нет, то вставьте в правую часть.
- Обе стороны заполнены, поэтому мы начинаем новый уровень, вставив в левую сторону.
Поскольку функция заполняет узлы вверх слева направо и сверху вниз, тогда мы всегда знаем (это инвариант), что левая сторона должна заполняться раньше правой, и что левая сторона никогда не может быть более чем на один уровень глубже правой сторона (и не может быть меньше правой стороны).
Наблюдая за ростом второго набора примеров деревьев, вы можете увидеть, как значения вставляются после этого инварианта. Этого достаточно для рекурсивного описания процесса, поэтому он экстраполирует на список любого размера (рекурсия - это маги c).
Теперь, как мы можем определить, является ли дерево «полным»? Что ж, оно завершено, если оно идеально сбалансировано или если - визуально - его значения образуют треугольник. Поскольку мы работаем с бинарными деревьями, то основание треугольника (при заполнении) должно иметь число значений, равное степени два. Более конкретно, он должен иметь значения 2^(depth-1). Подсчитайте сами в примерах:
depth = 1 -> base = 1: 2^(1-1) = 1depth = 2 -> base = 2: 2^(2-1) = 2depth = 3 -> base = 4: 2^(3-1) = 4depth = 4 -> base = 8: 2^(4-1) = 8
Общее количество узлов над основанием на единицу меньше ширины основания: 2^(n-1) - 1. Таким образом, общее количество узлов в полном дереве - это количество узлов над базой плюс число узлов в базе, поэтому:
num nodes in complete tree = 2^(depth-1) - 1 + 2^(depth-1)
= 2 × 2^(depth-1) - 1
= 2^depth - 1
Итак, теперь мы можем сказать, что дерево завершено, если оно имеет точно 2^depth - 1 непустые узлы в нем.
Поскольку мы go слева направо, сверху вниз, когда левая сторона завершена, мы двигаемся вправо, а когда вправо сторона так же полна, как и левая сторона (это означает, что она имеет такое же количество узлов, что означает, что она также завершена из-за инварианта), тогда мы знаем, что все дерево завершено, и, следовательно, должна быть добавлена новая строка.
У меня изначально было три особых случая: когда оба узла пусты, когда левый узел пуст (и, следовательно, так был правый), и когда правый узел пуст (и, следовательно, левый не может быть). Эти три особых случая заменяются последним случаем с охранниками:
- Если обе стороны пусты, то
countNodes left == countNodes right, поэтому мы добавляем еще одну строку (слева). - Если левая сторона пуста, то обе стороны пусты (см. Предыдущую точку).
- Если правая сторона пуста, то левая сторона должна иметь глубину 1 и количество узлов 1, то есть завершено, и
1 /= 0, поэтому мы добавляем к правой стороне.