- Теория по АВЛ-деревьям: http://ifmohm.googlepages.com/AVL_Trees.pdf
- Должно быть уже написано:
procedure pullUp(var root : PTreeNode; n : PTreeNode); - root -- корень упорядоченного дерева
- выполняется подъем вершины n на один уровень вверх (свойство упорядоченности сохраняется)
- Задание на 3
procedure balance(var root : PTreeNode; n : PTreeNode); - root -- корень дерева
- вершина n разбалансирована
- выполняется балансировка вершины n
- для тестирования выполнить полную балансировку дерева вручную
- Задание на 4
function partialAdd(var root : PTreeNode; x : TData) : PTreeNode; - root -- корень сбалансированного дерева
- если значение x не присутствует в дереве, оно добавляется в дерево
- ипраляется значение баланса в вершинах от добавленной до первой разбалансировки
- до корня, если ни одна вершина не оказалась разбалансированной
- функция возвращает самую нижнюю вершину, в которой в результате добавления нарушился баланс, если такая есть
- nil, если баланс во всех вершинах остался допустимым
- Задание на 5
procedure addAVL(var root : PTreeNode; x : TData); - добавление в АВЛ-дерево с последующим восстановлением баланса
- значения баланса всех веришн вычисляются правильно
|
|