VPF::Реализовать программу, создающую AVL дерево. Функц

RiG1

Дата 11.12.2011, 00:33 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 9
Регистрация: 4.12.2011

Репутация: нет
Всего: нет

Неодходимо реализовать программу, создающую 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 дерево)
Тут то и возникла проблема. Я не имею представления как это сделать. И ещё хотелось бы как можно графически вывести дерево на экран в консоли. Прошу помощи у вас.

Экскалупатор

Дата 11.12.2011, 02:45 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 1746
Регистрация: 1.4.2009
Где: г. Минск

Репутация: 11
Всего: 24

в википедии про балансировку расписано довольно подробно, методы "вращения", даже картинки нарисованы из какого состояния к какому нужно привести. с чем именно проблема?

по поводу вывода: проще всего, на мой взгляд, выводить в консоль дерево что бы его вершина была слева. для этого нужно опуститься в одну из ветвей до конца, при этом подсчитать сколько уровней пришлось пройти, и перед выводом добавить в строку количество отступов равное уровню узла. и повторять эту операцию пока не выведешь все дерево.
должно получится как то так:

                             101
                    100
                             90
           75
                    60
50(вершина)
                    36
           30
                    5
                             4

RiG1

Дата 11.12.2011, 12:31 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 9
Регистрация: 4.12.2011

Репутация: нет
Всего: нет

Про вращение я кое что понял, но я не могу даже представить как это реализовать в коде...

RiG1

Дата 12.12.2011, 01:20 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 9
Регистрация: 4.12.2011

Репутация: нет
Всего: нет

в Данный момент написал такие классы

Код


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;
    }

Имеется метод Add
Помогите дописать поиск по дереву и вывод его на экран

1 Пользователей читают эту тему (1 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| Общие вопросы по .NET и C# \| Следующая тема »