Балансировка АВЛ-дерева

@Kreativ · Регистрация: 22.09.2012

Доброй ночи, пытаюсь написать балансировку дерева, нашел статью с примерами, но дерево не балансируется, пожалуйста укажите ошибку, код класса:

C#

    public class Tree<T> where T : IComparable<T>
    {
        protected class Node
        {
            public T Value
            {
                get;
                set;
            }
            public T Key
            {
                get;
                set;
            }
            public int Height
            {
                get;
                set;
            }
            public Node Left
            {
                get;
                set;
            }
            public Node Right
            {
                get;
                set;
            }
 
            public Node(T value, T key)
            {               
                this.Value = value;
                this.Key = key;
                this.Height = 1;
            }
        }
 
        protected Node root;
 
        private int height(Node node)
        {
            return node != null ? node.Height : 0;
        }
        private int bfactor(Node node)
        {
            return height(node.Right) - height(node.Left);
        }
        private void fixheight(Node node)
        {
            int hl = height(node.Left);
            int hr = height(node.Right);
 
            node.Height = (hl > hr? hl : hr)+1;
        }
        private Node rotateright(Node p) // правый поворот вокруг p
        {
            Node q = p.Left;
            p.Left = q.Right;
            q.Right = p;
            fixheight(p);
            fixheight(q);
 
            return q;
        }
        private Node rotateleft(Node q) // левый поворот вокруг q
        {
            Node p = q.Right;
            q.Right = p.Left;
            p.Left = q;
            fixheight(q);
            fixheight(p);
 
            return p;
        }
        private Node balance(Node p) // балансировка узла p
        {
            fixheight(p);
            if (bfactor(p) == 2)
            {
                if (bfactor(p.Right) < 0)
                    p.Right = rotateright(p.Right);
                return rotateleft(p);
            }
            if (bfactor(p) == -2)
            {
                if (bfactor(p.Left) > 0)
                    p.Left = rotateleft(p.Left);
                return rotateright(p);
            }
            return p; // балансировка не нужна
        }
        public void AddElement(T newElement, T elements_key)
        {
            if (root == null) 
            {
                root = new Node(newElement, elements_key);
                balance(root);
                return;
            }
            AddElementRecursion(root, newElement, elements_key);
            
        }
    
        private void AddElementRecursion(Node currentNode, T newElement, T elements_key)
        {
            if (currentNode.Key.CompareTo(elements_key) > 0) 
            {
                if (currentNode.Left == null)
                {
                    currentNode.Left = new Node(newElement, elements_key);
                    balance(root);
                }
                else 
                    AddElementRecursion(currentNode.Left, newElement, elements_key);
            }
            else 
            {
                if (currentNode.Right == null) 
                {
                    currentNode.Right = new Node(newElement, elements_key);
                    balance(root);
                }
                else 
                    AddElementRecursion(currentNode.Right, newElement, elements_key);
            }
        }
    }

Добавлено через 12 часов 20 минут
выяснил, что не выполняется условие, но не могу понять почему:

C#

1
2
3

if (bfactor(p) == 2)
//и
 if (bfactor(p) == -2)

@kodv · 14.01.2013, 16:50

А что этот bFactor должен возвращать? Он возвращает разность между свойствами Height левого и правого узла. Height, в вашем случае, всегда равен 1 (либо вы что то здесь утаиваете). Следовательно, значение метода bFactor может принимать одно из трех значений: -1, 0, 1. То есть, данный метод никогда не вернет ни 2, ни -2.

@Kreativ · 14.01.2013, 16:52 **[ТС]**

видимо это ошибка в той статье, где я смотрел, буду искать дальше, не очень получается понять как сбалансировать дерево

Psilon · 14.01.2013, 22:03

Kreativ, совет: используйте автосвойства в одну строчку, тогда объявленые поля займут в 5 раз меньше места, т.к. вместо 5 строк будут занимать одну. И постарайтесь выделять похожие места в один метод, например

C#

        private void AddElementRecursion(Node currentNode, T newElement, T elements_key)
        {
            if (currentNode.Key.CompareTo(elements_key) > 0) 
            {
                if (currentNode.Left == null)
                {
                    currentNode.Left = new Node(newElement, elements_key);
                    balance(root);
                }
                else 
                    AddElementRecursion(currentNode.Left, newElement, elements_key);
            }
            else 
            {
                if (currentNode.Right == null) 
                {
                    currentNode.Right = new Node(newElement, elements_key);
                    balance(root);
                }
                else 
                    AddElementRecursion(currentNode.Right, newElement, elements_key);
            }
        }

спокойно преобразуется к виду

C#

        private void AddElementRecursion(Node currentNode, T newElement, T elements_key)
        {
            if (currentNode.Key.CompareTo(elements_key) > 0)             
                HelpMethod(currentNode.Left, newElement, elements_key)
            else 
                HelpMethod(currentNode.Right, newElement, elements_key)
        }
 
 
 
void HelpMethod(Node node, T newElement, T elements_key)
{
   if (node == null) 
   {
      node = new Node(newElement, elements_key);
      balance(root);
   }
   else 
      AddElementRecursion(node, newElement, elements_key);
}

Можно было бы рефакторить и дальше (например, потому что параметры по цепочке передаются сквозь метод), но даже это уменьшает объем кода в полтора раза и делает его яснее (разве что название вспомогательного метода хреновое, но лень думать).

Причем по сути вызов метода можно вообще в одну строку записать (расписал в 4 тупо для ясности).

C#

private void AddElementRecursion(Node currentNode, T newElement, T elements_key)
{
   HelpMethod(currentNode.Key.CompareTo(elements_key) > 0 ? currentNode.Left : currentNode.Right, newElement, elements_key)
}

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

@Kreativ · 15.01.2013, 00:55 **[ТС]**

ух, из 23 строк сократить настолько, надеюсь стиль выработается, чувствую, если вы будете смотреть мои посты, то я точно начну так писать ) Это уже не первый раз, когда вы обращаете моё внимание на это. Буду стараться писать грамотней.

Psilon · 15.01.2013, 01:11

Не по теме:

Kreativ, да ну :D Не повезло вам со мной. А я вот не замечаю, кому что говорю :D

Почитайте про рефакторинг (Мартин Фаулер "Рефакторинг. Улучшение существующего кода", еще есть книжечка "чистый код"), очень прочищает мозги. Тогда не надо будет на своих ошибках учиться. Как говорит народная мудрость "умный учится на чужих ошибках, глупый - на своих, дурак - ни на каких не учится". Я надеюсь, что вы пойдете первым путем, хотя бы потому, что такие люди как вы меня окружают, а общаться с умными интереснее

Добавлено через 5 минут
И еще: у элементов есть не свойство Height, а свойство Level, Height - свойство дерева и подчиняется уравнению
Height = Max(Level)

Добавлено через 4 минуты
Не подумайте, что придираюсь

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

C#

        private int bfactor(Node node)
        {
            return height(node.Right) - height(node.Left);
        }

Можно сделать методом самого Node

C#

        public int bfactor()
        {
            return Right.Height - Left.Height; //Хотя вроде уже сказал, что лучше Level
        }

ну а в классе написать простое делегирование

C#

        private int bfactor(Node node)
        {
            return node.bfactor()
        }

И если такая заглушка уже перестает быть нужной (она ничего не делает, только перепоручает метод другому объекту) её можно удалить, заменив все вызовы "встраиванием метода". Ну и так далее

@Kreativ · 15.01.2013, 01:26 **[ТС]**

не, на самом деле спасибо

. Я на уровне классов толком не работал, поэтому такая каша..., код из статьи в интернете взял, даже толком и не разобрался - не работает он как надо. Книги стоит почитать, в любом случае мне вас "окружать"

но даже и не знаю как все успеть то ли C# то ли C++ учить.

Psilon · 15.01.2013, 01:36

Kreativ, С++ живет только за счет того, что в некоторых случаях он быстрей и на нем наработана очень большая база. И если второе еще как-то его держит на плаву (хотя на Java уже 1ккк девайсов, а зная шарп можно сказать, что значете и джаву), то производительность все больше уходит в прошлое (самсунг пару дней назад аннонсировал 8-ядерный процессор для мобильных телефонов). Так что я бы в сторону С++ даже не смотрел

Когда там такой код

C++

1 2	result.erase(std::unique(result.begin(), result.end()), result.end()); std::stable_sort(result.begin(), result.end(), lessThan);

или даже такой:

C++

1 2	if (cmd[1] == RESET) // если принятая команда RESET {((void(*)(void))0)();} // что-то из черной магии

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

@Kreativ · 15.01.2013, 01:46 **[ТС]**

Сообщение от Psilon

что-то из черной магии

я под столом

, оказывается мои познания в С++ настолько ничтожны))) Вообще отбросить С++, даже как то страшно)) а стоит ли изучать Java + C# вместе или же лучше вначале одно затем другое

@kodv 1447 / 1119 / 345 Регистрация: 11.04.2011 Сообщений: 2,615
	14.01.2013, 16:50	2
	А что этот bFactor должен возвращать? Он возвращает разность между свойствами Height левого и правого узла. Height, в вашем случае, всегда равен 1 (либо вы что то здесь утаиваете). Следовательно, значение метода bFactor может принимать одно из трех значений: -1, 0, 1. То есть, данный метод никогда не вернет ни 2, ни -2. 0

@Kreativ 2 / 2 / 0 Регистрация: 22.09.2012 Сообщений: 202
	14.01.2013, 16:52 [ТС]	3
	видимо это ошибка в той статье, где я смотрел, буду искать дальше, не очень получается понять как сбалансировать дерево 0

@Kreativ 2 / 2 / 0 Регистрация: 22.09.2012 Сообщений: 202
	15.01.2013, 00:55 [ТС]	5
	ух, из 23 строк сократить настолько, надеюсь стиль выработается, чувствую, если вы будете смотреть мои посты, то я точно начну так писать ) Это уже не первый раз, когда вы обращаете моё внимание на это. Буду стараться писать грамотней. 0

@Kreativ 2 / 2 / 0 Регистрация: 22.09.2012 Сообщений: 202
	15.01.2013, 01:26 [ТС]	7
	не, на самом деле спасибо . Я на уровне классов толком не работал, поэтому такая каша..., код из статьи в интернете взял, даже толком и не разобрался - не работает он как надо. Книги стоит почитать, в любом случае мне вас "окружать" но даже и не знаю как все успеть то ли C# то ли C++ учить. 0

@Kreativ 2 / 2 / 0 Регистрация: 22.09.2012 Сообщений: 202
	15.01.2013, 01:46 [ТС]	9
	Сообщение от Psilon что-то из черной магии я под столом, оказывается мои познания в С++ настолько ничтожны))) Вообще отбросить С++, даже как то страшно)) а стоит ли изучать Java + C# вместе или же лучше вначале одно затем другое 0