2 / 2 / 0
Регистрация: 22.09.2012
Сообщений: 202
1

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

14.01.2013, 11:43. Показов 7601. Ответов 8
Метки нет (Все метки)

Доброй ночи, пытаюсь написать балансировку дерева, нашел статью с примерами, но дерево не балансируется, пожалуйста укажите ошибку, код класса:
C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
    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)
__________________
Помощь в написании контрольных, курсовых и дипломных работ, диссертаций здесь
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
14.01.2013, 11:43
Ответы с готовыми решениями:

Балансировка дерева
Как сделать балансировку бинарного дерева поиска? template &lt;class T, class I&gt; class node {...

Балансировка двоичного дерева
В файле дана последовательность целых чисел. Построить из них двоичное дерево поиска . Разработать...

Балансировка бинарного дерева
Попалась одна на вид простая задача. Код написал, но не проходит 10 тестов из 40. Лидеру команды...

Балансировка AVL дерева
Здравствуйте. У меня возникла такая проблема, не могу сбалансировать AVL дерево, верней даже не...

8
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
2 / 2 / 0
Регистрация: 22.09.2012
Сообщений: 202
14.01.2013, 16:52  [ТС] 3
видимо это ошибка в той статье, где я смотрел, буду искать дальше, не очень получается понять как сбалансировать дерево
0
Master of Orion
Эксперт .NET
6091 / 4947 / 905
Регистрация: 10.07.2011
Сообщений: 14,522
Записей в блоге: 5
14.01.2013, 22:03 4
Kreativ, совет: используйте автосвойства в одну строчку, тогда объявленые поля займут в 5 раз меньше места, т.к. вместо 5 строк будут занимать одну. И постарайтесь выделять похожие места в один метод, например
C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
        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#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
        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#
1
2
3
4
private void AddElementRecursion(Node currentNode, T newElement, T elements_key)
{
   HelpMethod(currentNode.Key.CompareTo(elements_key) > 0 ? currentNode.Left : currentNode.Right, newElement, elements_key)
}
И сразу приходит понимание, что это метод лишний, потому что занимается тупым делегированием. А значит, нужно заниматься выделением класса, вводить туда новые параметры и метод помещать туда.
1
2 / 2 / 0
Регистрация: 22.09.2012
Сообщений: 202
15.01.2013, 00:55  [ТС] 5
ух, из 23 строк сократить настолько, надеюсь стиль выработается, чувствую, если вы будете смотреть мои посты, то я точно начну так писать ) Это уже не первый раз, когда вы обращаете моё внимание на это. Буду стараться писать грамотней.
0
Master of Orion
Эксперт .NET
6091 / 4947 / 905
Регистрация: 10.07.2011
Сообщений: 14,522
Записей в блоге: 5
15.01.2013, 01:11 6

Не по теме:

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


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

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

Добавлено через 4 минуты
Не подумайте, что придираюсь Если коротко: у вас только проблемы с рефакторингом: если есть методы, которые используют поля чужого класса и не используют свои, то эти завистливые методы следует поместить в тот класс, до которого они так домогаются. Например метод
C#
1
2
3
4
        private int bfactor(Node node)
        {
            return height(node.Right) - height(node.Left);
        }
Можно сделать методом самого Node
C#
1
2
3
4
        public int bfactor()
        {
            return Right.Height - Left.Height; //Хотя вроде уже сказал, что лучше Level
        }
ну а в классе написать простое делегирование
C#
1
2
3
4
        private int bfactor(Node node)
        {
            return node.bfactor()
        }
И если такая заглушка уже перестает быть нужной (она ничего не делает, только перепоручает метод другому объекту) её можно удалить, заменив все вызовы "встраиванием метода". Ну и так далее
0
2 / 2 / 0
Регистрация: 22.09.2012
Сообщений: 202
15.01.2013, 01:26  [ТС] 7
не, на самом деле спасибо . Я на уровне классов толком не работал, поэтому такая каша..., код из статьи в интернете взял, даже толком и не разобрался - не работает он как надо. Книги стоит почитать, в любом случае мне вас "окружать" но даже и не знаю как все успеть то ли C# то ли C++ учить.
0
Master of Orion
Эксперт .NET
6091 / 4947 / 905
Регистрация: 10.07.2011
Сообщений: 14,522
Записей в блоге: 5
15.01.2013, 01:36 8
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)();} // что-то из черной магии
Причем после курения манов если и можно понять, что это особая команда, специфичная для контроллера, причем завязанная на ассемблер, то мне этим просто не хочется заниматься, да и жить после чтения такого кода не хочется
0
2 / 2 / 0
Регистрация: 22.09.2012
Сообщений: 202
15.01.2013, 01:46  [ТС] 9
Цитата Сообщение от Psilon Посмотреть сообщение
что-то из черной магии
я под столом, оказывается мои познания в С++ настолько ничтожны))) Вообще отбросить С++, даже как то страшно)) а стоит ли изучать Java + C# вместе или же лучше вначале одно затем другое
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
15.01.2013, 01:46
Помогаю со студенческими работами здесь

Высота авл дерева - как считать?
Добрый вечер. Забавно. Предположим, что пустой указатель равен -1, высота пр - высота лев. ...

Комменты к реализации Красно-черного и АВЛ дерева
Люди добрые помогите разобрать и по возможности написать комментарии к этим 2м кодам .. Это коды...

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

Балансировка DNS
Добрый день, форумчане. Такой вопрос. Имеется 2 ПК, на обоих установлен &quot;защищенный&quot; Suse, на одном...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
9
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2022, CyberForum.ru