Скачать: CL | DM;

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

← →
Равшан   (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]

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

---

← →
MBo ©   (2007-04-30 19:54) [5]

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

---

← →
ferr ©   (2007-04-30 19:56) [6]

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

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

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

---

Страницы: 1 вся ветка

Скачать: CL | DM;



Память: 0.46 MB
Время: 0.037 c