ЛР3. АВЛ-дерево

МИНОБРНАУКИ РОССИИ

Санкт-Петербургский государственный

электротехнический университет

«ЛЭТИ» им. В.И. Ульянова (Ленина)

отчЁт

по лабораторной работе №3

по дисциплине «Алгоритмы и структуры данных»

Тема: АВЛ-дерево.

Студент гр. 9300		ФИО
Преподаватель		Виноградов Д.

Санкт-Петербург

2020

BinaryTreeNode.java

Описывает класс узла бинарного дерева.

package j.lab3.tree.node; import j.lab3.tree.BinaryTree; @SuppressWarnings("unchecked") public class BinaryTreeNode<T extends BinaryTreeNode<T>> { public int value; public T parent, left, right; public BinaryTreeNode(int value) { this.value = value; } // Поиск узла по значению public T searchNode(int value) { T result = (T) this; while (result != null && value != result.value) { if (value < result.value) result = result.left;

else result = result.right; } return (T) result; } // Поиск узла с минимальным значением public T minNode() { T result = (T) this; while (result.left != null) result = result.left; return result; } // Поиск узла с максимальным значением public T maxNode() { T result = (T) this; while (result.right != null) result = result.right; return result; } // Поиск последователя public T getSuccessor() { // Возвращаем минимальные узел в правом поддереве, если оно есть... if (right != null) return right.minNode(); // ...если же его нет, то ищем родителя, у которого сын будет слева. T son = (T) this; T parent = this.parent; while (parent != null && parent.right == son) { son = parent; parent = parent.parent; } return parent; } // Удаление узла из дерева public void delete(BinaryTree<T> tree) { // Если нет потомков: if (left == null && right == null) { if (tree.root != this) { if (parent.left == this) parent.left = null; else parent.right = null; } else tree.root = null; } // Если один потомок слева: else if (left != null && right == null) { if (tree.root != this) { if (parent.left == this) parent.left = left; else parent.right = left; } else tree.root = left; left.parent = parent; } // Если один потомок справа: else if (left == null) { if (tree.root != this) { if (parent.left == this) parent.left = right; else parent.right = right; } else tree.root = right; right.parent = parent; } // Если два потомка: else { // Копируем значение последователя в узел. Удаляем последователя. T successor = getSuccessor(); value = successor.value; successor.delete(tree); } } }

BinaryTree.java

Описывает класс бинарного дерева.

package j.lab3.tree; import j.lab3.tree.node.BinaryTreeNode; @SuppressWarnings("unchecked") public class BinaryTree<T extends BinaryTreeNode<T>> { public T root; protected T createNode(int value) { return (T) new BinaryTreeNode<T>(value); } // Вставка нового узла в дерево public T insert(int value) { // Создаём новый узел. T inserted = createNode(value); // Если дерево пустое, задаём ему корень и заканчиваем. if (root == null) return root = inserted; // Ищем узел, который будет предком для вставляемого узла. T parent = root; while (true) { // Если значение меньше, идём налево. if (value < parent.value) { if (parent.left == null) { parent.left = inserted; // Соединяем найденного предка с созданным узлом. break; } parent = parent.left; } // Если значение больше или равно, идём направо. else { if (parent.right == null) { parent.right = inserted; // Соединяем найденного предка с созданным узлом. break; } parent = parent.right; } } // Соединяем созданный узел с найденным предком. inserted.parent = parent; return inserted; } // Удаление узла с указанным значением public T remove(int value) { T removed = root.searchNode(value); removed.delete(this); return removed; } }

AVLTreeNode.java

Наследуется от BinaryTreeNode и описывает класс узла АВЛ-дерева.

package j.lab3.tree.node; import j.lab3.tree.AVLTree; public final class AVLTreeNode extends BinaryTreeNode<AVLTreeNode> { public int height = 0; public int balance = 0; public AVLTreeNode(int value) { super(value); } // Обновление баланса и высоты public void updateHeightAndBalance() { height = Math.max(left == null ? 0 : left.height, right == null ? 0 : right.height) + 1; balance = (right == null ? 0 : right.height) - (left == null ? 0 : left.height); } // Восстановление баланса public void restoreBalance(AVLTree tree) { // Обновляем высоту и баланс. this.updateHeightAndBalance(); // Слева выше, чем справа. if (this.balance < -1) { if (left.balance < 0) this.rotateRight(tree); else this.rotateLeftRight(tree); } // Слева ниже, чем справа. else if (this.balance > 1) { if (right.balance > 0) this.rotateLeft(tree); else this.rotateRightLeft(tree); } } // Правый поворот public void rotateRight(AVLTree tree) { AVLTreeNode left = this.left; // Соединяем _опорный_ узел с правым потомком _левого_ узла. this.left = left.right; if (left.right != null) left.right.parent = this; // Соединяем предка _опорного_ узла с _левым_ узлом. left.parent = this.parent; if (this.parent == null) tree.root = left; else if (this.parent.right == this) this.parent.right = left; else this.parent.left = left; // Соединяем _опорный_ узел с _левым_ узлом, // чтобы _левый_ стал предком для _опорного_. left.right = this; this.parent = left; // Обновим высоты и балансы. this.updateHeightAndBalance(); left.updateHeightAndBalance(); } // Левый поворот public void rotateLeft(AVLTree tree) { AVLTreeNode right = this.right; // Соединяем _опорный_ узел с левым потомком _правого_ узла. this.right = right.left; if (right.left != null) right.left.parent = this; // Соединяем предка _опорного_ узла с _правым_ узлом. right.parent = this.parent; if (this.parent == null) tree.root = right; else if (this.parent.right == this) this.parent.right = right; else this.parent.left = right; // Соединяем _опорный_ узел с _правым_ узлом, // чтобы _правый_ стал предком для _опорного_. right.left = this; this.parent = right; // Обновим высоты и балансы. this.updateHeightAndBalance(); right.updateHeightAndBalance(); } // Левый-правый поворот public void rotateLeftRight(AVLTree tree) { left.rotateLeft(tree); this.rotateRight(tree); } // Правый-левый поворот public void rotateRightLeft(AVLTree tree) { right.rotateRight(tree); this.rotateLeft(tree); } }

AVLTree.java

Наследуется от BinaryTree и описывает класс АВЛ-дерева.

package j.lab3.tree; import j.lab3.tree.node.AVLTreeNode; public class AVLTree extends BinaryTree<AVLTreeNode> { @Override protected AVLTreeNode createNode(int value) { return new AVLTreeNode(value); } @Override // Вставка нового узла в дерево public AVLTreeNode insert(int value) { // Вставляем узел в двоичное дерево. AVLTreeNode inserted = super.insert(value); // Восстанавливаем баланс по пути // от нового узла к корню дерева. AVLTreeNode current = inserted; while (current != null) { current.restoreBalance(this); current = current.parent; } return inserted; } @Override // Удаление узла с указанным значением public AVLTreeNode remove(int value) { // Удаляем узел из двоичного дерева. AVLTreeNode removed = super.remove(value); // Восстанавливаем баланс по пути // от удалённого узла к корню. AVLTreeNode current = removed; while (current != null) { current.restoreBalance(this); current = current.parent; } return removed; } }