Форум программистов, компьютерный форум, киберфорум
Наши страницы

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Nullik
43 / 12 / 1
Регистрация: 13.03.2013
Сообщений: 300
Завершенные тесты: 1
#1

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

10.11.2013, 10:31. Просмотров 683. Ответов 3
Метки нет (Все метки)

Добрый вечер.

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

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

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

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

Добавлено через 10 часов 18 минут
Апп
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
10.11.2013, 10:31
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Высота авл дерева - как считать? (C++):

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

Высота бинарного дерева - C++
Надо найти высоту бинарного дерева.

Высота n-нарного дерева - C++
Подскажите алгоритм нахождения высоты n-нарного дерева, я написала, но высота находится не всегда точно. Не знаю как избежать этого. ...

Высота бинарного дерева поиска - C++
Что неправильно в программе? Полное условие #include <iostream> #include <cstdio> #pragma comment (linker,...

Как в АВЛ-дереве найти самую короткую ветвь и удалить ее? - C++
Доброго времени суток. Нужна помощь. В АВЛ-дереве надо найти самую короткую ветвь и удалить ее. Я могу удалить только узел по ключу (ну...

Как считать определённое количество цифр заданного числа (считать число до заданной цифры)? - C++
как считать число 12345 до символа 5? То есть 1234 присвоить другой переменной?.:wall:

3
ya_noob
_
313 / 147 / 9
Регистрация: 08.10.2011
Сообщений: 432
10.11.2013, 11:47 #2
Цитата Сообщение от Nullik Посмотреть сообщение
как посчитать высоту авл дерева
так же как и любого другого дерева: высота дерева равна наибольшей из высот его поддеревьев + 1
Цитата Сообщение от Nullik Посмотреть сообщение
Просто я считаю, считаю и у меня везде 0, а где 1???
А как вы считаете?
0
Nullik
43 / 12 / 1
Регистрация: 13.03.2013
Сообщений: 300
Завершенные тесты: 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 -- что не так делаю?
0
ya_noob
_
313 / 147 / 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.
может быть надо было найти разность высот в поддеревьях? если так, то теперь это делается вычитанием полученных высот
0
10.11.2013, 14:37
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
10.11.2013, 14:37
Привет! Вот еще темы с ответами:

АВЛ-дерево - C++
Из входной последовательности символов построить АВЛ-дерево без повторов. Найти в нем узел, относительно которого будет максимальная...

АВЛ дерево - C++
Здравствуйте. Я начинающий программист и мне нужна помощь. Сейчас пытаюсь понять тему АВЛ деревьев и попробовала забить этот код, но к...

АВЛ дерево и коллизия хэша - C++
До некоторых пор думал, что красно-черное и авл деревья, да и вообще любые структуры, позволяющие сделать нечто вида: printf("%d\n",...

Запись бинарного дерева в файл и восстановление из него этого дерева - C++
Задача такая: есть бинарное дерево. Каждый элемент дерева содержит 3 указателя - 1 указатель на структуру с данными, 2 и 3й указатель на...


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

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

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2018, vBulletin Solutions, Inc.
Рейтинг@Mail.ru