Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 5.00/11: Рейтинг темы: голосов - 11, средняя оценка - 5.00
215 / 63 / 25
Регистрация: 30.04.2013
Сообщений: 866
Записей в блоге: 10
1

Сбалансированное не бинарное дерево

10.01.2016, 22:38. Показов 2106. Ответов 3
Метки нет (Все метки)

Каково определение сбалансированного произвольного, не бинарного дерева ?

Например, для бинарного говориться, что расхождение высот для любого узла должно быть не более единицы.

Добавлено через 5 минут
http://stackoverflow.com/quest... ogarithmic

Кажется нашел ответ здесь,


when talking about an m'ary tree, we have to use log m(n) to get the actual height. E.g. a balanced tree where each node has three children has a log3(n) height.


Но, мне не очень понятна идея с расхождениями
как они считаются и как эти расхождения применить к m-арному случаю ?
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
10.01.2016, 22:38
Ответы с готовыми решениями:

Сбалансированное дерево (бинарное)
кто сможет, пожалуйста напишите код с++, построения сбалансированного дерева,функцию добавления...

Сбалансированное бинарное дерево. Структуры даннных
Доброе время суток,уважаемые посетители форума! Задали на структурах данных создать...

Сформировать идеально сбалансированное бинарное дерево
Дан текст программы. Проверти правильно или нет описание сделал? TNode*...

Сформировать идеально сбалансированное бинарное дерево и найти в нем максимальный элемент
Далее преобразовать его в дерево поиска и тоже найти максимальный элемент.

3
2620 / 2209 / 236
Регистрация: 03.07.2012
Сообщений: 7,979
Записей в блоге: 1
10.01.2016, 22:51 2
О каких расхождениях пишет ТC?
0
471 / 423 / 290
Регистрация: 10.03.2015
Сообщений: 1,782
10.01.2016, 22:54 3
zer0mail, на сколько я понял, речь идет о бинарном дереве поиска.
Сбалансированное дерево подразумевает расхождения в количестве элементов правого и левого поддерева на не более чем 1.

Про формулировку сбалансированное не бинарное дерево первый раз слышу, сказать ничего не могу)
0
215 / 63 / 25
Регистрация: 30.04.2013
Сообщений: 866
Записей в блоге: 10
11.01.2016, 09:23  [ТС] 4
Цитата Сообщение от SuperKir Посмотреть сообщение
сбалансированное не бинарное дерево первый раз слышу
тоже самое, в лекциях сейчас читаю , вижу определение аналогичное для бинарного дерева :


Дерево называется сбалансированным, если оно m-арно и для каждого узла разница между максимальными и минимальными путями его под-деревьев не превосходит единицы.


Обычно пытаюсь все, написанное в лекциях сопоставить каким либо другим источникам(книжки, wikipedia, др. статьи и-нета ). Но для данного случая, найти аналогичное определение не удалось. Кроме, как нечто похожее на stackoverflow. Вопрос в том, следует ли (и, если да, то как?) из определения на данном сайте (stackoverflow) определение данное в лекциях.

Добавлено через 1 минуту
Цитата Сообщение от Qazan Посмотреть сообщение
Дерево называется сбалансированным, если оно m-арно и для каждого узла разница между максимальными и минимальными путями его под-деревьев не превосходит единицы.
данное определение я понимаю, интересует обоснование

Добавлено через 40 минут
1. https://en.wikipedia.org/wiki/K-ary_tree

2. stackoverflow.com:What is the total number of nodes in a full k-ary tree, in terms of the number of leaves?

думаю второе, должно привести к истине.
Наверное, нужно рассуждать мол, что если расхождение в мин и макс путях более единицы ?
Тогда, (полное) m-арное дерево теряет как минимум (m + 1) узлов.

https://www.cyberforum.ru/cgi-bin/latex.cgi?<br />
1. N(m - 1) + 1 = m^{h + 1}  // for\ full\ m-ary\ tree<br />
2. N*m - N + 1 - (m + 1) = m^h * m  \rightarrow <br />
    N*m - N - m = m^h * m \rightarrow<br />
    N(1  - 1/m) - 1 = m^h // [1/m] = 0 <br />
    <br />
ну и тут, что называется приплыли
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
11.01.2016, 09:23

Сформировать идеально сбалансированное бинарное дерево, тип информационного поля - double
Привет, кто сможет помочь? 1. Сформировать идеально сбалансированное бинарное дерево, тип...

Исходное бинарное дерево превратить в бинарное дерево поиска, при этом сохранив его структуру
Помогите, не могу понять!( Нужно исходное бинарное дерево превратить в бинарное дерево поиска, при...

Сбалансированное дерево
Неупорядоченную последовательность из n различных чисел изобразить в виде сбалансированного дерева....

Сбалансированное дерево
Всем привет!) Для учебной практики требуется решить задачу: Написать программу в С++, суть...

Сбалансированное дерево
Ребят, может есть у кого код сбалансированного дерева с подробными комментариями, чтобы...

Идеально сбалансированное дерево
Интересует как работает этот кусок кода) по идеи Create(&amp;tmp-&gt;right, nr); сюда компилятор никогда...


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

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

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