среда, 02 июня 2010
20:54

Проверка сбалансированности бинарного дерева

все записи пользователя в сообществе vadimpirov
Подскажите пожалуйста алгоритм проверки сбалансированности бинарного дерева.

Есть простое бинарное дерево

@темы: Вопрос, C++, Алгоритм

URL
Комментарии
02.06.2010 в 21:31

Южени
Сострада- тельный черный - анекдот в двух словах.(с)
Ну вроде того, но не проще ли делать дерево сбалансированным по мере добавления записей, каждый раз корректируя? Такой алгоритм очень подробно расписан у Кнута, например (:
URL
02.06.2010 в 21:43



Листья - 1, 4, 6, 9. Их длины отличаются лишь на единицу.
Но это не сбалансированное дерево.
URL
02.06.2010 в 22:36

vadimpirov
нужно просто написать функцию, которая возвращает : сбаланс. \ не сбаланс.
как можно реализовать?
URL
02.06.2010 в 22:50

Южени
Сострада- тельный черный - анекдот в двух словах.(с)
Вообще-то, насколько я помню, сбалансированное дерево - это такое деревце, у которого в КАЖДОМ узле длины левого и правого поддеревьев отличаются не более, чем на 1, соответственно надо как-то рекурсивно пройтись по всему дереву, попутно проверяя на всех узлах.)
URL
02.06.2010 в 23:12

Южени
Вот я и о том же.
А предложенный вариант с длинами какой-то странный.
URL
03.06.2010 в 00:07

Южени
Сострада- тельный черный - анекдот в двух словах.(с)
Феаринг ну это просто человек наверняка не стал вникать в смысл определений - внешне ж всё просто.
URL
03.06.2010 в 01:19

vadimpirov
а не могли бы расписать алгоритм, хотя бы словами?!

функция обхода уже есть

void Node::Scan_Nisxod(void (*f)(void* n))
{
f(this->Data);
std::cout<Left != NULL) this->Left->Scan_Nisxod(f);
if (this->Right != NULL) this->Right->Scan_Nisxod(f);
}
URL
03.06.2010 в 10:49

Мне лень писать.

У тебя есть вершина и два поддерева. Тебе для каждой вершины нужно решить три вопроса:
- является ли правое поддерево АВЛ деревом?
- является ли левое поддерево АВЛ деревом?
- разница длин правого и левого поддеревьев различается не больше чем на единицу?

Вот тебе и алгоритм. Переходишь в вершину, запускаешь алгоритм для обоих потомков, вычисляешь высоту поддеревьев, сравниваешь.
Если все ок - то возвращаешь ок.
URL
03.06.2010 в 21:51

vadimpirov
кто то советовал *проходим от корня к листьям, считаем длину пути до каждого листа. если максимальная разбежка в высотах = 1 то дерево сбалансирован*

нашел тут ru.wikipedia.org/wiki/B-%D0%B4%D0%B5%D1%80%D0%B...

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


следовательно предложенный способ верен!!??
URL
03.06.2010 в 22:14

Южени
Сострада- тельный черный - анекдот в двух словах.(с)
ru.wikipedia.org/wiki/%D0%A1%D0%B1%D0%B0%D0%BB%...

По идее оно такое.
URL