Форум программистов, компьютерный форум CyberForum.ru

Высота авл дерева - как считать? - C++

Восстановить пароль Регистрация
 
Nullik
 Аватар для Nullik
43 / 12 / 1
Регистрация: 13.03.2013
Сообщений: 297
Завершенные тесты: 1
10.11.2013, 10:31     Высота авл дерева - как считать? #1
Добрый вечер.

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

А как посчитать высоту авл дерева с таким набором: 5, 3, 6, 2, 4?

----5[?]
--3[?]---6[?]
2[?]--4[?]

Т.е., простройте мне это дереао с самого начала, как его высота измняется.
Просто я считаю, считаю и у меня везде 0, а где 1???

Добавлено через 10 часов 18 минут
Апп
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
10.11.2013, 10:31     Высота авл дерева - как считать?
Посмотрите здесь:

Высота n-нарного дерева C++
Как удалить корень дерева? C++
АВЛ дерево и коллизия хэша C++
C++ АВЛ-дерево
Написать шаблон бинарного дерева с функцией распечатки дерева C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
ya_noob
_
200 / 144 / 9
Регистрация: 08.10.2011
Сообщений: 432
10.11.2013, 11:47     Высота авл дерева - как считать? #2
Цитата Сообщение от Nullik Посмотреть сообщение
как посчитать высоту авл дерева
так же как и любого другого дерева: высота дерева равна наибольшей из высот его поддеревьев + 1
Цитата Сообщение от Nullik Посмотреть сообщение
Просто я считаю, считаю и у меня везде 0, а где 1???
А как вы считаете?
Nullik
 Аватар для Nullik
43 / 12 / 1
Регистрация: 13.03.2013
Сообщений: 297
Завершенные тесты: 1
10.11.2013, 12:17  [ТС]     Высота авл дерева - как считать? #3
Цитата Сообщение от ya_noob Посмотреть сообщение
так же как и любого другого дерева: высота дерева равна наибольшей из высот его поддеревьев + 1

А как вы считаете?
1)
----5[0]
высота у 5 = 0.

2)
----5[1]
--3[0]

высота у 3 = 0
у 5 = 0 - (-1) = 1

3)
----5[0]
--3[0]---6[0]

3 = 0,
6 = 0,
5 = 0 - 0 = 0.

4)
----5[1]
--3[1]---6[0]
2[0]

2 = 0,
3 = 0 - (-1) = 1,
6 = 0,
5 = 1 - 0 = 1.

5)
----5[0]
--3[0]---6[0]
2[0]--4[0]

2 = 0,
4 = 0,
3 = 0 - 0 = 0,
6 = 0,
5 = 0 - 0 = 0.

Но ведь в 5 должна быть 1 -- что не так делаю?
ya_noob
_
200 / 144 / 9
Регистрация: 08.10.2011
Сообщений: 432
10.11.2013, 14:37     Высота авл дерева - как считать? #4
зачем ты вычитаешь высоты в поддеревьях? чтобы найти высоту, надо определять максимальную из высот в поддеревьях:
1)
----5[0]
высота у 5 = max((-1), (-1)) + 1 = 0.
2)
----5[1]
--3[0]
высота у 3 = max((-1), (-1)) + 1 = 0.
у 5 = max(0, (-1)) + 1 = 1
3)
----5[0]
--3[0]---6[0]
3 = 0,
6 = max((-1), (-1)) + 1 = 0,
5 = max(0, 0) + 1 = 1.
4)
----5[1]
--3[1]---6[0]
2[0]
2 = max((-1), (-1)) + 1 = 0,
3 = max(0, (-1)) + 1 = 1,
6 = 0,
5 = max(1, 0) + 1 = 2.
5)
----5[0]
--3[0]---6[0]
2[0]--4[0]
2 = 0,
4 = max((-1), (-1)) + 1 = 0,
3 = max(0, 0) + 1 = 1,
6 = 0,
5 = max(1, 0) + 1 = 2.
может быть надо было найти разность высот в поддеревьях? если так, то теперь это делается вычитанием полученных высот
Yandex
Объявления
10.11.2013, 14:37     Высота авл дерева - как считать?
Ответ Создать тему
Опции темы

Текущее время: 07:08. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru