1 / 1 / 1
Регистрация: 07.04.2019
Сообщений: 41
1

Сделать вывод AVL дерева

13.06.2019, 21:15. Показов 4632. Ответов 1
Метки нет (Все метки)

Не получается сделать наглядный вывод дерева. В traverse_debug ошибка не могу ее исправить.
Вот полный код. Ошибка: tuple index out of range. Возникает когда выбираю 3 кейс.

Python
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
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
class AVLNode:
    def __init__(self, key, parent=None):
        self.key=key
        self.parent=parent
        self.left=None
        self.right=None
        self.height=1
        pass
 
    def get_balance(self):
        l=self.left.height if self.left else 0
        r=self.right.height if self.right else 0
        return l-r
 
    def update_height(self):
        l = self.left.height if self.left else 0
        r = self.right.height if self.right else 0
        self.height=max(l,r)+1
        pass
 
    def insert(self,key):
        if key<self.key:
            if not self.left:
                self.left=AVLNode(key,self)
                return self
            else:
                return self.left.insert(key)
        else:
            if not self.right:
                self.right=AVLNode(key,self)
                return self
            else:
                return self.right.insert(key)
        pass
 
    def traverse(self):
        if self.left:
            self.left.traverse()
        print(self.key, end='')
        if self.right:
            self.right.traverse()
        pass
 
    def traverse_debug(self):
        print('{1}<{0}[{3}]({4})>{2}'.format(self.key,
                                             self.left.key if self.left else None,
                                             self.get_balance(),
                                             self.height))
        if self.left:
            self.left.traverse_debug()
        if self.right:
            self.right.traverse_debug()
        pass
 
    def find_min(self):
        return self if not self.left else self.left.find_min()
 
    def find(self,key):
        if key==self.key:
            return self
        elif key<self.key:
            if not self.left:
                return None
            else:
                return self.left.find(key)
        else:
            if not self.right:
                return None
            else:
                return self.right.find(key)
    pass
 
pass
 
class AVLTree:
    def __init__(self):
        self.root=None
        pass
 
    def restore_balance(self, node):
        if not node:
            return
        h=node.height
        node.update_height()
        b=node
        if node.get_balance()==-2:
            if node.right.get_balance()==1:
                self.right_rotate(node.right)
            b=self.left_rotate(node)
        elif node.get_balance==2:
            if node.left.get_balance()==-1:
                self.left_rotate(node.left)
            b=self.right_rotate(node)
        if b.height!=h or abs(b.get_balance())>1:
            self.restore_balance(b.parent)
        pass
 
    def left_rotate(self,x):
        y=x.right
        x.right=y.left
        if y.left: y.left.parent=x
        y.left=x
        y.parent=x.parent
        x.parent=y
        x.update_height()
        y.update_height()
        p=y.parent
        if not p:
            self.root=y
        elif p.left is x:
            p.left=y
        else:
            p.right=y
        return y
    pass
 
    def right_rotate(self,x):
        y=x.left
        x.left=y.right
        if y.right: y.right.parent=x
        y.right=x
        y.parent=x.parent
        x.parent=y
        x.update_height()
        y.update_height()
        p=y.parent
        if not p:
            self.root=y
        elif p.left is x:
            p.left=y
        else:
            p.right=y
        return y
    pass
 
    def delete(self, key):
        if not self.root:
            print('Ошибка удаления. Дерево пусто.')
            return
        found=self.root.find(key)
        if not found:
            print('Ошибка удаления. Удаляемый ключ не найдет.')
            return
        if found.left and found.right:
            found.key=found.right.find_min().key
            self.delete(found.key)
            return
        if not found.left and not found.right:
            alt=None
        elif not found.left:
            alt=found.right
        else:
            alt=found.left
        p=found.parent
        if alt:
            alt.parent=p
        if not p:
            self.root=alt
        else:
            if p.left is found:
                p.left=alt
            else:
                p.right=alt
        self.restore_balance(p)
    pass
 
    def insert(self, key):
        if not self.root:
            self.root = AVLNode(key)
        else:
            self.restore_balance(self.root.insert(key))
    pass
 
    def traverse(self):
        if not self.root:
            print('Пусто')
        else:
            self.root.traverse()
            print()
    pass
 
    def traverse_debug(self):
        if not self.root:
            print('Пусто')
        else:
            print('#Формат вывода.',
                  '\n #левый потомок < текущий узел[баланс](высота)>(правый потомок)')
            self.root.traverse_debug()
    pass
 
pass
 
command=[
    '1-Добавить элемент',
    '2-Удалить элемент',
    '3-Вывести дерево с отладочной информацией',
    '0-Выход',
]
 
tree=AVLTree()
 
while True:
    print('Элементы дерева[мин -> макс]:')
    tree.traverse()
    print()
    for i in command:
        print(i)
    print()
 
    choice=input("Выбор действия:")
    if choice =='0':
        break
    elif choice =='1':
        tree.insert(int(input('Введите значение: ')))
    elif choice =='2':
        tree.delete(int(input('Введите значение: ')))
    elif choice =='3':
        tree.traverse_debug()
    else:
        print('Неверное действие. Повторите попытку.', end='')
    print()
__________________
Помощь в написании контрольных, курсовых и дипломных работ, диссертаций здесь
0
Лучшие ответы (1)
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
13.06.2019, 21:15
Ответы с готовыми решениями:

Удаление из AVL-дерева
Узел дерева: namespace AVL_Tree { /// &lt;summary&gt; /// Узел дерева. /// &lt;/summary&gt; ...

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

Физическое удаление из AVL-дерева
Можно ли при удалении сначала провести балансировку и пересчитать балансы, а потом произвести...

Графическое представление AVL дерева
Пытаюсь реализовать графическое представление AVL дерева. Swing знаю более 3-х дней. Понимаю...

1
1281 / 667 / 364
Регистрация: 07.01.2019
Сообщений: 2,176
13.06.2019, 21:33 2
Лучший ответ Сообщение было отмечено asd360 как решение

Решение

Вот ошибка

Python
1
2
3
4
print('{1}<{0}[{3}]({4})>{2}'.format(self.key,
                                             self.left.key if self.left else None,
                                             self.get_balance(),
                                             self.height))
Вы пытаетесь вывести элемент с индексом 4, а задаете всего 4 элемента, то есть у последнего индекс 0
1
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
13.06.2019, 21:33
Помогаю со студенческими работами здесь

Удаление узла из AVL-дерева
Почему можно так (стр 28) сделать ? Добавлено через 2 минуты Как вообще может найтись такой...

Проверить на эквивалентность два AVL-дерева
Такое вот задание: проверить на эквивалентность два АВЛ-дерева. Если они не являются информационно...

Функция удаления всех четных элементов AVL-дерева
Помогите допилить функцию удаления всех парных элементов АВЛ дерева. Она сейчас удаляет только...

Как сделать вывод всех элементов 2-3 дерева?
Использовал реализацию 2-3 дерева с Хабра. Но вообще не могу разобраться, не знаю как сделать вывод...


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

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

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