Добавление элемента в сбалансированное бинарное дерево.

← →
Равшан (2007-04-30 16:33) [0]

Как добавить с помощью функции Add(int) элемент в дерево, чтобы оно было сбалансированным? Сначала делал с помощью флажка f - поочередно налево, потом направо добавлялось. Но потом понял что при кол-ве элементов большим 7 неправильно работает.
class Element { public: int data; Element* left; Element* right; Element(); Element(int); }; void Tree::Add(int a) { if(root == NULL) { root = new Element(a); return; } AddElement(root, a); } void Tree::AddElement(Element* p, int a) { if (p->left == NULL) { p->left = new Element(a); return; } if (p->right == NULL) { p->right = new Element(a); return; } if (f) { f=0; AddElement(p->right, a); } else { f=1; AddElement(p->left, a); } }

← →
MBo © (2007-04-30 17:03) [1]

Непонятно, есть ли у тебя отношение порядка (ключ больше-меньше)
Для упорядоченных деревьев стоит использовать структуры данных, в которых поддерживается баланс - это, например, черно-красные (RB-tree) и AVL-деревья. http://algolist.manual.ru/

← →
MBo © (2007-04-30 17:06) [2]

P.S. Если большая часть элементов известна заранее, и динамическое добавление не сыграет большой роли, можно использовать алгоритм из Вирта для создания сбалансированного дерева из (упорядоченного) массива
http://delphimaster.net/view/2-1176964506/

← →
Равшан (2007-04-30 19:44) [3]

Спасибо. Разобрался.

← →
Равшан (2007-04-30 19:46) [4]

А как вывести дерево на экран в виде дерева?

В горизонтальном виде - рекурсивным обходом в порядке preorder получится
H
-L
--LL
--LR
-R
--RL
--RR
если привычное представление требуется - придется посчитать листья для правильного масщтабирования-выравнивания

> P.S. Если большая часть элементов известна заранее, и динамическое
> добавление не сыграет большой роли, можно использовать
> алгоритм из Вирта для создания сбалансированного дерева
> из (упорядоченного) массива

Никогда б не подумал что об этом ещё и где-то написано. Казалось что вещь само-собой разумеющаяся.

Автору скорее совет на алголист не ходить а поискать эти темы в талмудах или книжёнках. Я б например посоветовал книгу "Готовые алгоритмы в Delphi" с теннисными мячиками на абложке, там дан неплохой готовый код для AVL, или если есть время то можно разобраться с теорией, например с RB, в Кормене...

Добавление элемента в сбалансированное бинарное дерево. Найти похожие ветки