Учитывая следующие отсортированные целые числа: 1 2 3 4 5 6 7 8. Как бы вы построили сбалансированное дерево поиска?построение сбалансированного дерева
Я был бы очень признателен, если кто-то может объяснить с, не давая примеры кода.
Это не домашнее задание. Я делаю ревизию для экзамена.
Если значения, указанные выше, помещаются в сбалансированное дерево, должно ли дерево выглядеть так, как показано ниже?
5
4 6
3 7
2 8
1
Вы можете думать о строительстве снизу вверх.
У вас будет корень. Если в дереве есть только один элемент, это корень. Каждый элемент в корне будет иметь ссылку на еще два узла в дереве (двоичное дерево). Один для элемента, большего, чем он сам, а другой для элемента, меньшего самого себя.
Так что если вы дерево имеет только номер один, и вы собираетесь вставить номер паклю, это будет вставлено как лист, и ссылка «больше, чем» в корневом каталоге будет указывать на узел 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
Самый простой способ, вероятно, следующее:
Поскольку ваш список целых чисел уже отсортирован, вы можете просто выбрать значение посередине, чтобы найти среднее значение (и нет необходимости перемещать любые значения вокруг среднего, когда вы разбиваете). Вы получаете поддеревья, просто разделив список на две части.
Последнее дерево зависит от того, какой узел вы выбираете как средний. Это один из примеров:
4
2 6
1 3 5 7
8
Как следует дерево как после сборки? похоже на мой ответ? (Проверить вопрос только что отредактирован) – Harminder
Это очень хорошая идея. В конце вы выбираете элемент поворота сортированного списка. Splendid. Это можно использовать даже при создании дерева из гистограммы. Ницца. –
Это на самом деле отличный пример, можете ли вы дать схему каждого шага? как после вставки 2 дерева должно выглядеть как 1> 2 так далее? – Harminder
Это не очень хороший пример. Сначала вы говорите, что вы строите дерево снизу вверх, но вы этого не делаете. Затем вы делаете это, вставляя один узел за раз и «исправляя». Это возможно, но эти исправления довольно сложны. Например, красное черное дерево делает это и должно обрабатывать множество разных случаев. – rasmus