Лабораторная работа VII «Бинарные деревья»
Узел:
function createTreeNode(key, value = key) {
return {
key,
value,
left: null,
right: null
};
}
Функции:
function bstInsert(root, key, value) {}
function bstSearch(root, key) {}
function bstMin(root) {}
function bstMax(root) {}
function bstDelete(root, key) {}
function treeHeight(root) {}
Обходы:
-
preorder;
-
inorder;
-
postorder;
-
обход по уровням.
Студент должен реализовать как минимум один обход рекурсивно и один итеративно.
Обязательный эксперимент: вставить ключи сначала в случайном, затем в отсортированном порядке. Сравнить высоту дерева и число сравнений поиска.
Именно здесь становится наглядной мысль: название структуры «двоичное дерево поиска» само по себе не гарантирует логарифмическую работу; эффективность зависит от высоты.
Дополнительный уровень: бинарная куча в массиве и очередь с приоритетом.