Реализовать программу, создающую AVL дерево. Функции добавления узлов и поиск по дереву - C#
Формулировка задачи:
Неодходимо реализовать программу, создающую AVL дерево. Функции добавления узлов и поиск по дереву. Т.к. понятних для меня исходников не нашел, решил писать сам.
Вот текущий код
Как я понял из алгоритма добавления вершины
после добавления вершины методом Add необходимо проверить балансировку дерева и отбалансировать его(Чтобы это было именно AVL дерево)
Тут то и возникла проблема. Я не имею представления как это сделать. И ещё хотелось бы как можно графически вывести дерево на экран в консоли. Прошу помощи у вас.
using System; using System.Collections.Generic; using System.Linq; using System.Text; namespace AVL { class Program { static void Main(string[] args) { AVLTree a = new AVLTree(); a.Add(1); a.Add(4); a.Add(2); a.PrintTree(); Console.ReadKey(true); } } public class AVLTree { int num; // номер узла AVLTree left; AVLTree right; public void TreeConstr(int n) { num = n; left = right = null; } // метод вывода дерева на экран public void PrintTree() { Console.WriteLine(num); if (left != null) { left.PrintTree(); } if (right != null) { right.PrintTree(); } } // метод добавления узла в дерево public void Add(int n) { if (n < num) { if (left == null) { left = new AVLTree(); left.TreeConstr(n); } else { left.Add(n); } } if (n > num) { if (right == null) { right = new AVLTree(); right.TreeConstr(n); } else { right.Add(n); } } } } }
Прохода по пути поиска, пока не убедимся, что ключа в дереве нет.
Включения новой вершины в дерево и определения результирующих показателей балансировки.
"Отступления" назад по пути поиска и проверки в каждой вершине показателя сбалансированности. Если необходимо - балансировка.
ап ап
ап ап ап
ап ап
Решение задачи: «Реализовать программу, создающую AVL дерево. Функции добавления узлов и поиск по дереву»
textual
Листинг программы
public class AVLNode { // конструктор public AVLNode(String name) { value = name; } public String value; // значение public int height; // высота public AVLNode left; // левое дерево public AVLNode right; // правое дерево } public class AVLTree { // конструктор public AVLTree() { root = null; } // метод добавления узла, принимает строку value public void insert(String value) { /* Если root = null, то создаем новый корневой узел */ // Рут это значение корневого узла if (root == null) root = new AVLNode(value); // сравниваем текущее значение со значением корневого узла // и в соответствии с этим добавляем в левое или правое поддерево int compareResult = value.CompareTo(root.value); if (compareResult < 0) { root.left.value = value; // присваиваем значение // проверяем балансировку // если высота левого дерева - высота правого дерева == 2 то if (root.left.height - root.right.height == 2) // если текущее значение меньше root.left.value if (value.CompareTo(root.left.value) < 0) // то выполняем одно вращение влево singleRotation(root, 0); else // в противном случае выполняем 2 вращения влево doubleRotation(root, 0); // в противном случае если результат сравнения со значением корнегого узла >0 else if (compareResult > 0) { root.right.value = value; // присваиваем значение // если высота правого - высота левого == 2 if (root.right.height - root.left.height == 2) { // если текущее значение меньше root.right.value if (value.CompareTo(root.right.value) > 0) root = singleRotation(root, 1); else root = doubleRotation(root, 1); } } // высота дерева root.height = Math.Max(root.left.height, root.right.height) + 1; } } // одно вращение private AVLNode singleRotation(AVLNode node, int side) { AVLNode temp = node; // Just to declare if (side == 0) // Левое вращение { temp = node.left; node.left = temp.right; temp.right = node; node.height = Math.Max(node.left.height, node.right.height) + 1; temp.height = Math.Max(temp.left.height, node.height) + 1; } else if (side == 1) // Правое вращение { temp = node.right; node.right = temp.left; temp.left = node; node.height = Math.Max(node.left.height, node.right.height) + 1; temp.height = Math.Max(temp.right.height, node.height) + 1; } return temp; } private AVLNode doubleRotation(AVLNode node, int side) { if (side == 0) //Двойное левое вращение { node.left = singleRotation(node.left, 1); return singleRotation(node, 0); } else if (side == 1) //Двойное правое вращение { node.right = singleRotation(node.right, 0); return singleRotation(node, 1); } return node; } public AVLNode SearchNode(String value, AVLNode node) { if (root == null) return null; else { if (node.value == value) return node; else if (value.CompareTo(node.value) < 0) return SearchNode(value, root.left); else return SearchNode(value, root.right); } } private AVLNode root; }
ИИ поможет Вам:
- решить любую задачу по программированию
- объяснить код
- расставить комментарии в коде
- и т.д