key: 1, 6, 8, 10, 20, 21, 25, 30.

Если организовать древовидную структуру со следующим распределением ключей (N=NULL)

			10
	6				25				Р
1	8		20					30
								И
N N	N	N	N	21			N	N
			N		N		У
			Рис. 8.2			Г
				Б
то обход дерева в симметричном порядке организуется функцией
void WrtTree(TTree **p)		// p - указатель на текущий узел дерева
{
if (*p == NULL) return;		// Если дочь отсутствует, то выход
}			к
WrtTree((&(*p)->A1));
< Print(p^.Inf); > // При симметричном обходе печать ставить здесь
WrtTree((&(*p)->A2));			а
	т		нап чатана информация в порядке возрас-
При вызове этой функции буд

тания ключа. Если в процедуре поменять местами А1 и А2, то информация будет напечатана в порядке убывания ключа.

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

значения ключалу евого преемника меньше, чем у правого. Таким образом, органи- зованное дерево по уч о название двоичное дерево поиска. Ввиду его своеобраз- ной организациибэффект вность поиска информации в такой динамической струк-

туре данных сравнима с эффективностью двоичного поиска в массиве, т.е. О(log n).

Замет м, что двоичный поиск в линейном связанном списке организовать невоз- можно, а эффективность линейного поиска имеет порядок О(n/2).

и 2

БКонечно, оценка О(log2n) справедлива для сбалансированного дерева, т.е. такого, у которого узлы, имеющие только одну дочь, располагаются не выше двух последних уровней.

8.4. Основные операции с двоичным деревом поиска

При организации списков в виде двоичного дерева необходим пакет про- грамм, реализующих следующие действия:

-поиск заданного ключа;

-поиск минимального (максимального) ключа;

PDF created with pdfFactory Pro trial version www.pdffactory.com

-вставка нового значения ключа, не изменяя свойств дерева поиска;

-удаление заданного ключа;

-формирование дерева поиска;

-балансировка дерева.

Поиск в двоичном дереве по заданному ключу Inf.key: void PoiskTree(TTree *p, int k, bool *bl, TInf *Res)

{

if ((p != NULL) && (*bl != true)) {

if (p->Inf.key != k)

{

Р

PoiskTree(p->A1,k, bl, Res);

PoiskTree(p->A2,k, bl, Res);

И

}

else

{

У

*bl=true;

*Res =

p->Inf;

Г

}

Б

}

}

а

Поиск информации с минимальным (м ксим льным) ключом:

TInf MinKey(TTree *p)

к

{

while (p->A1 != NULL) p = p->A1;

return p->Inf;

т

}

При поиске максимальногоеключа нужно спуститься по правой ветке

чей:

го

(p:=p^.A2) до самого прав

лис а.

и

Вставить новый элемент с ключом key, не совпадающим ни с одним из клю-

void MakeList(TTree **p, TInf Inf) // Создание нового листа дерева

{

б

и

*p = new TTree;л

(*p)->Inf = Inf;

Б

(*p)->A1=NULL; (*p)->A2=NULL;

}

//---------------------------------------------------------------------------

void DobTree(TTree *proot, TInf Inf) // Добавление листа в дерево

{

TTree *p = proot, *q; bool bl;

while (p != NULL) {

PDF created with pdfFactory Pro trial version www.pdffactory.com

q = p;

bl = ( Inf.key < p->Inf.key); if (bl) p = p->A1;

else p = p->A2;

}

		MakeList(&p, Inf);
	}	if (bl) q->A1=p; else q->A2=p;
			Р
	Построение дерева поиска:
			И
		Пусть имеется некоторый массив из n значений данных с разными ключами

	a:array[1..n] of Tinf. Построение дерева поиска можно осуществить следующим
	образом:		У
	MakeList(&proot,A[1]);	Г
	for(int i=2; i<=n; i++) DobTree(proot,A[i]);
		Б

При случайном чередовании ключей в массиве а обычно формируется дере- во, достаточно хорошо сбалансированное. Однако, если ключи в исходном масси- ве а частично упорядочены, то дерево поиска оказывается сильно разбалансиро-

ванным и его эффективность для организ ции поиска оказывается сравнимой с

линейным поиском в массиве.						к
	Этот способ построения дерева поис можно использовать для печати
					е
элементов массива (например располож анного в файле) в порядке возрастания.
Для этого достаточно построить и расп чатать полученное дерево.
				т
	Построение сбалансированного дерева поиска для заданного массива а
можно осуществить, если э					массив предварительно отсортирован в порядке
возрастания ключа.			и
	Следующая рекурс вная процедура строит идеально сбалансированное де-
рево поиска по отсорт рованному массиву:
	void MakeBlns(TTree **p, int k, int l, TInf A[ ])
{		б
	и
	if (k==l) { *p =лNULL;
	Б	return;

}

else {

int m=(k+l)/2;

*p = new TTree; (*p)->Inf =A[m];

MakeBlns((&(*p)->A1),k,m,A);

MakeBlns((&(*p)->A2),m+1,l,A);

}

}

PDF created with pdfFactory Pro trial version www.pdffactory.com

Удаление узла с заданным ключом из дерева поиска, сохраняя его свойства.

При решении этой задачи следует рассматривать три разные ситуации: 1. Удаление листа с ключом key:

	5						5
	key	8			N			8
N	N								Р
2. Удаление узла, имеющего одну дочь:
									И
	5				5			У
							Г
	key				Б
				а		7
	7	N
				к
			е
3. Удаление узла, имеющего двух доч рей, зн чительно сложнее. Если p – исклю-
чаемый узел, то его следует заменить узлом w, который содержит наибольший
	p		т

ключ в левом поддереве p (либо наим ньший ключ в правом поддереве). Такой узел w является либо листом, либо самым правым узлом поддерева p, у которого

			7	о				6
имеется только левая дочь:
			и
		л			Удалить	7
	б				9		4		9
	4
и		w
Б					10				10
2		6		8		2	5	8
	5		N					N

void UdTree(TTree **proot, TInf Inf)

{

TTree *p = *proot, *q = p, *w, *v; // Поиск удаляемого узла

while ((p != NULL) && (p->Inf.key != Inf.key)) {

PDF created with pdfFactory Pro trial version www.pdffactory.com

q = p;

if (p->Inf.key > Inf.key) p = p->A1;

else p = p->A2;

}

if (p == NULL) return; // Если узел не найден, то выход

// Если узел не имеет дочерей

if ((p->A1 == NULL) && (p->A2 == NULL)){

if (p == q) *proot = NULL;

else

Р

if (q->A1 == p) q->A1 = NULL;

else q->A2 = NULL;

И

else

}

// Если узел имеет дочь слева

У

if (p->A1 == NULL) {

Г

if (p == q) *proot = p->A2;

Б

else

if (q->A1 == p) q->A1 = p->A2;

}

else q->A2 = p->A2;

ва

else

// Если узел имеет дочь спр

if (p->A2 == NULL) {

к

if (p == q) *proot = p->A1;

else

т

if (q->A2 == p) q->A2 =еp->A1;

о

}

else q->A1 = p->A1;

и

else

// Если узел меет двух дочерей

{

w = p->A1;

б

if (w->A2 == NULL) w->A2 = p->A2;

и

elseл{

Б

do {

v = w;

w = w->A2;

} while (w->A2 != NULL);

v->A2 = w->A1; w->A1 = p->A1; w->A2 = p->A2;

}

if (p == *proot) *proot = w;

PDF created with pdfFactory Pro trial version www.pdffactory.com