💡 Во-первых, надо понимать отличие простого двоичного поискового дерева от сбалансированного.
Двоичное дерево поиска называется сбалансированным по высоте, если для каждой его вершины высоты левого и правого поддеревьев различаются не больше, чем на $1$.
➡ В теории структур данных такие деревья называют AVL-tree.
Сейчас я покажу $2$ сбалансированных по высоте двоичных дерева поиска.
Рисунок — сбалансированное по высоте двоичное дерево поиска
Рисунок — идеально сбалансированное двоичное дерево поиска
💡 Во-вторых, при построении бинарного дерева из массива оно должно получаться автоматически сбалансированным, то есть при добавлении очередной вершины не нужно выполнять специальную операцию, называемую балансировкой.
💡 В-третьих, построение дерева не должно зависеть от количества элементов массива. Речь про четное или нечетное количество элементов массива. То есть алгоритм формирования дерева должен быть универсальным ( это одно из базовых свойств алгоритма — массовость ).
💡 В-четвертых, обязательно массив чисел, на основе которого получается дерево, должен быть отсортирован. Если это условие не выполняется, то полученное дерево не будет являться сбалансированным ( будут перекосы ).
Для анализа алгоритма построения бинарного дерева из массива возьму такие данные:
| $5$ | $8$ | $12$ | $20$ | $33$ | $38$ | $49$ | $50$ | $77$ | $91$ | $99$ | значение | |
| $0$ | $1$ | $2$ | $3$ | $4$ | $5$ | $6$ | $7$ | $8$ | $9$ | $10$ | индекс | |
Всего в массиве $11$ целых чисел. Они упорядочены по возрастанию! Эти числа образуют последовательность на отрезке от $0$ до $10$ ( беру значения по индексам ).
➡ Формирование дерева будет происходить рекурсивно, так как это максимально удобно.
На каждом этапе я буду выбирать «центральный» элемент. Его индекс легко рассчитать по формуле: $\frac{[левая\ граница]\ +\ [правая\ граница]}{2}$.
➡ Этап #$1$.
Находим индекс центрального элемента: $\frac{0\ +\ 10}{2} = 5$. Значение этого элемента равно $38$. Очевидно, что вершина с этим значением будет корнем двоичного сбалансированного по высоте дерева.
| $5$ | $8$ | $12$ | $20$ | $33$ | $38$ | $49$ | $50$ | $77$ | $91$ | $99$ | значение | |
| $0$ | $1$ | $2$ | $3$ | $4$ | $5$ | $6$ | $7$ | $8$ | $9$ | $10$ | индекс | |
Числа, которые меньше $38$ ( $5,\ 8,\ 12,\ 20,\ 33$ ), будут добавлены в левое поддерево относительно корня, большие ( $49,\ 50,\ 77,\ 91,\ 99$ ), будут добавлены в правое поддерево.
➡ Этап #$2$.
Находим индекс «центрального» элемента, расположенного в левой части, относительно значения $38$: $\frac{0\ +\ 4}{2} = 2$. Значение этого элемента равно $12$.
| $5$ | $8$ | $12$ | $20$ | $33$ | $38$ | $49$ | $50$ | $77$ | $91$ | $99$ | значение | |
| $0$ | $1$ | $2$ | $3$ | $4$ | $5$ | $6$ | $7$ | $8$ | $9$ | $10$ | индекс | |
💡 Есть такой нюанс, связанный с поведением рекурсивной функции, которая формирует дерево. Дело в том, что сначала строятся узлы левого поддерева, а затем достраиваются вершины из правого поддерева. По этой причине на этапе #$3$ сначала будут добавляться вершины в левое поддерево относительно узла $12$.
➡ Этап #$3$.
Индекс центрального элемента: $\frac{0\ +\ 1}{2} = 0$. Значение этого элемента равно $5$.
| $5$ | $8$ | $12$ | $20$ | $33$ | $38$ | $49$ | $50$ | $77$ | $91$ | $99$ | значение | |
| $0$ | $1$ | $2$ | $3$ | $4$ | $5$ | $6$ | $7$ | $8$ | $9$ | $10$ | индекс | |
➡ Этап #$4$.
Индекс центрального элемента: $\frac{1\ +\ 1}{2} = 1$. Значение этого элемента равно $8$.
| $5$ | $8$ | $12$ | $20$ | $33$ | $38$ | $49$ | $50$ | $77$ | $91$ | $99$ | значение | |
| $0$ | $1$ | $2$ | $3$ | $4$ | $5$ | $6$ | $7$ | $8$ | $9$ | $10$ | индекс | |
➡ Этап #$5$.
Индекс центрального элемента: $\frac{3\ +\ 4}{2} = 3$. Значение этого элемента равно $20$.
| $5$ | $8$ | $12$ | $20$ | $33$ | $38$ | $49$ | $50$ | $77$ | $91$ | $99$ | значение | |
| $0$ | $1$ | $2$ | $3$ | $4$ | $5$ | $6$ | $7$ | $8$ | $9$ | $10$ | индекс | |
➡ Этап #$6$.
Индекс центрального элемента: $\frac{4\ +\ 4}{2} = 4$. Значение этого элемента равно $33$.
| $5$ | $8$ | $12$ | $20$ | $33$ | $38$ | $49$ | $50$ | $77$ | $91$ | $99$ | значение | |
| $0$ | $1$ | $2$ | $3$ | $4$ | $5$ | $6$ | $7$ | $8$ | $9$ | $10$ | индекс | |
➡ В результате левое поддерево относительно корня ( вершина с ключом $38$ ) отстроено. Аналогичным образом формируется и правое поддерево.
На следующей картинке показано конечное сбалансированное по высоте двоичное дерево поиска, построенное на основе данных из приведенного массива целых чисел:
Рисунок — полностью построенное сбалансированное бинарное дерево поиска
А вот программная реализация функции с подробными комментариями, которая формирует сбалансированное по высоте двоичное дерево из массива:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 |
//------------------------------------------------------------------------------ // рекурсивное построение сбалансированного бинарного дерева поиска из массива целых чисел // values - одномерный массив целых чисел, которые выступают в качестве ключей узлов дерева // index_left - индекс числа в массиве values - левая граница подпоследовательности чисел // index_right - индекс числа в массиве values - правая граница подпоследовательности чисел // в качестве результата функция вернет указатель на построенное сбалансированное двоичное дерево поиска // функция корректно работает с любым количеством чисел массива ( четное или нечетное - не важно ) //------------------------------------------------------------------------------ Node* Build_balance_BST_from_sorted_vector( const int values[], const int index_left, const int index_right ) { // отвечает за индекс числа массива values, которое будет добавляться в дерево int index_center; // указатель на вершину, которая добавляется в дерево Node* add_node = NULL; // элементарный случай рекурсии: когда все элементы текущей подпоследовательности чисел // уже добавлены в дерево, то заканчиваем функцию if ( index_left > index_right ) { return NULL; } // на каждом шаге выбираем центральный элемент подпоследовательности чисел index_center = ( index_left + index_right ) / 2; add_node = Create_node( values[ index_center ] ); // рекурсивно вызываем функцию, чтобы "достроить" левое и правое поддерево текущего узла add_node add_node -> left = Build_balance_BST_from_sorted_vector( values, index_left, index_center - 1 ); add_node -> right = Build_balance_BST_from_sorted_vector( values, index_center + 1, index_right ); // в качестве ответа возвращаем указатель на корень построенного сбалансированного двоичного дерева поиска return add_node; } //------------------------------------------------------------------------------ |
Пример вызова этой функции. В результате переменная root будет указывать на корень построенного сбалансированного двоичного дерева поиска.
|
1 2 3 |
const int N = 11; int values[] = { 5, 8, 12, 20, 33, 38, 49, 50, 77, 91, 99 }; root = Build_balance_BST_from_sorted_vector( values, 0, N - 1 ); |
А теперь несколько слов о вычислительной сложности приведенного алгоритма. Очевидно, что придется обратиться к каждому элементу массива, чтобы добавить соответствующую вершину в дерево.
В целом алгоритм состоит из $2$ этапов:
➡ Нахождение в массиве числа.
➡ Вставка вершины в дерево.
Первый этап имеет сложность $O( 1 )$, то есть выполняется мгновенно. Второй этап требует $O( log( n ) )$, причем как в лучшем, так в среднем или худшем случае, так как двоичное дерево поиска является сбалансированным по высоте. Количество вставок равно количеству элементов заданного массива, следовательно, общая вычислительная сложность алгоритма построения сбалансированного дерева из массива будет $O( n\ \cdot\ log( n ) )$, где $n$ — количество элементов массива.
Пишите в комментариях, что непонятно в рамках приведенного алгоритма. Также расскажите, в каких случаях вам приходилось строить бинарное дерево из массива.
| ВНИМАНИЕ | Для заказа программы на бинарное дерево ( поиска ) пишите на мой электронный адрес proglabs@mail.ru |
Добавить комментарий