Реализовать программу, создающую AVL дерево. Функции добавления узлов и поиск по дереву - C#

Узнай цену своей работы

Формулировка задачи:

Неодходимо реализовать программу, создающую 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);
                }
            }
        }
    }
}
Как я понял из алгоритма добавления вершины
Прохода по пути поиска, пока не убедимся, что ключа в дереве нет. Включения новой вершины в дерево и определения результирующих показателей балансировки. "Отступления" назад по пути поиска и проверки в каждой вершине показателя сбалансированности. Если необходимо - балансировка.
после добавления вершины методом Add необходимо проверить балансировку дерева и отбалансировать его(Чтобы это было именно AVL дерево) Тут то и возникла проблема. Я не имею представления как это сделать. И ещё хотелось бы как можно графически вывести дерево на экран в консоли. Прошу помощи у вас.
ап ап
ап ап ап
ап ап

Решение задачи: «Реализовать программу, создающую 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;
    }

ИИ поможет Вам:


  • решить любую задачу по программированию
  • объяснить код
  • расставить комментарии в коде
  • и т.д
Попробуйте бесплатно

Оцени полезность:

8   голосов , оценка 3.75 из 5
Похожие ответы