Vyhledávání III. - Binární vyhledávací stromy

Vyhledávání v BVS – operace SEARCH
Rekurzivní zápis vyhledávání
Nerekurzivní zápis vyhledávání
Vkládání prvku do BVS – operace INSERT
Rekurzivní zápis operace INSERT
Nerekurzivní zápis operace INSERT
Rušení prvku v BVS - operace DELETE
Rekurzivní zápis operace INSERT .

Binární vyhledávací strom (dále zkráceně BVS, anglicky – binary search tree) je takový binární uspořádaný strom, pro jehož každý uzel platí, že jeho levý podstrom je buď prázdný, nebo sestává z uzlů, hodnoty jejichž klíčů jsou menší než hodnota klíče daného uzlu a podobně jeho pravý podstrom je buď prázdný, nebo sestává z uzlů, hodnoty jejichž klíčů jsou větší než hodnota klíče daného uzlu.

V předcházející části kapitoly byla uvedena souvislost mezi nesekvenčním vyhledáváním v seřazeném poli a uspořádaným binárním stromem, která vyplývá ze stromové interpretace binárního a Fibonacciho vyhledávání. Vzájemnost tohoto vztahu doplňuje vlastnost průchodu typu INORDER binárním vyhledávacím stromem, kterým získáme seřazený lineární seznam.

Protože základní operací nad ATD tabulka je operace SEARCH a na ní závislá operace READ, budeme se nejdříve zabývat implementací těchto operací v BVS. Strom je typická dynamická datová struktura, a proto v dalších odstavcích rozebereme take operace INSERT a DELETE.

3.1. Vyhledávání v BVS – operace SEARCH

Nechť jsou dány typy:

	TYPUKUZEL = ^TYPUZEL;
	TYPUZEL = record
			DATA:TYPDATA;
			KLIC:TYPKLIC;
			LEVY, PRAVY: TYPUKUZEL
		       end;

Nechť je dále dán binární vyhledávací strom, jehož uzly jsou typu TYPUZEL a nechť je dána proměnná KOREN typu TYPUKUZEL, která ukazuje na kořen tohoto stromu. Algoritmus vyhledání uzlu stromu, jehož složka KLIC je shodná s vyhledávaným klíčem K typu TYPKLIC lze zapsat s pomocí rekurze nebo nerekurzivně.

3.1.1. Rekurzivní zápis vyhledávání

Princip rekurzivního zápisu algoritmu vyhledávání ve stromu je založen na rekurzivnosti datové struktury strom. Algoritmus má tvar:

	function SEARCH (KOREN:TYPUKUZEL; K:TYPKLIC):Boolean;
	{ Funkce má hodnotu true, jestliže v BVS daném ukazatelem KOREN existuje uzel, jehož 
  složka KLIC se rovná vyhledávanému klíči K }
begin
	if KOREN <> nil
		then if KOREN^.KLIC > K
			then SEARCH := SEARCH (KOREN^.LEVY, K) 
				{ hledej v levém podstromu }
			else SEARCH := SEARCH (KOREN^.PRAVY, K)
				{ hledej v pravém podstromu }
		else SEARCH := false;	{ cesta končí v listu – neúspěšné vyhledání }
end	{ funkce SEARCH }

Tato funkce odpovídá specifikaci operace SEARCH tak, jak byla uvedena v předcházející kapitole. Při praktické práci s ATD tabulka je však často vhodný takový druh operace, jehož vedlejším účinkem je v případě úspěšného vyhledávání lokalizace a zpřístupnění nalezeného prvku. Tohoto účinku se může využít k implementaci operace READ. Nechceme-li použít další parametr (např. parametr var KDE:TYPUKUZEL) pro zpřístupnění nalezeného prvku, můžeme pro tento účel použít parametr KOREN s vědomím, že procedura změní jeho původní hodnotu. Protože funkce s výstupními parametry odporuje zásadám správného programování, bude mít operace tvar procedury:

procedure SEARCHTREE (var KOREN:TYPUKUZEL; K:TYPKLIC);
{ Procedura hledá uzel s klíčem K ve stromu zadaném ukazatelem KOREN;
  najde-li uzel, zpřístupní ho ukazatelem KOREN, nenajde-li uzel, bude mít ukazatel 
  KOREN hodnotu nil }
begin
if KOREN <> nil
	then if KOREN^.KLIC <> K
		then begin
			if KOREN^.KLIC < K
				then KOREN := KOREN^.LEVY
				else KOREN := KOREN^.PRAVY;
			SEARCHTREE (KOREN, K)
		        end
end	{ procedury SEARCHTREE }

Po vyvolání procedury SEARCHTREE lze ustavit hodnotu Booleovské proměnné SEARCH na základě hodnoty parametru KOREN takto:

	SEARCH := KOREN <> nil;
	{ if SEARCH then ukazatel KOREN zpřístupňuje nalezený prvek tabulky }

Korektnější podoba této procedury bude mít čtyři parametry a tedy hlavičku:

	procedure SEARCHTREE (KOREN:TYPUKUZEL; K:TYPKLIC; var SEARCH:Boolean;
				     var KDE:TYPUKUZEL);

3.1.2. Nerekurzivní zápis vyhledávání

Nerekurzivní zápis algoritmu operace SEARCH má tvar:

	function SEARCH (KOREN:TYPUKUZEL; K:TYPKLIC):Boolean;
	var KONEC:Boolean;	{ pomocná proměnná pro řízení cyklu }
	begin
		SEARCH := false;
		KONEC := KOREN = nil;
		while not KONEC do
			begin
				if KOREN^.KLIC = K
					then begin	
KONEC := true; { úspěšné vyhledávání }
						SEARCH := true
					        end
					else if KOREN^.KLIC > K
						then KOREN := KOREN^.LEVY
							{ pokračuj v levém podstromu }
						else KOREN := KOREN^.PRAVY;
							{ pokračuj v pravém podstromu }
				if KOREN = nil then KONEC := true
			end
	end	{ procedury SEARCH }

Odvození nerekurzivního zápisu algoritmu operace SEARCHTREE, která v případě úspěšného vyhledání zpřístupní nalezený uzel stromu ponecháme čtenářům.

3.2. Vkládání prvku do BVS – operace INSERT

Podle sémantické definice přepíše operace INSERT hodnotu prvku, který byl v tabulce nalezen. Nebyl-li v tabulce nalezen prvek s daným klíčem, operace INSERT vloží do tabulky nový prvek v tímto klíčem. Je-li tabulka implementována binárním vyhledávacím stromem, končí neúspěšné vyhledávání právě na tom listu stromu, na který se má připojit nový prvek. Je-li neúspěšně vyhledaný klíč menší než klíč listu, připojí se nový uzel vlevo k danému listu, je-li větší, připojí se vpravo k danému listu. Algoritmus operace INSERT může mít rekurzivní i nerekurzivní zápis.

3.2.1. Rekurzivní zápis operace INSERT

Rekurzivní zápis procedury INSERT je velice krátký a přehledný:

procedure INSERT (var KOREN:TYPUKUZEL; K:TYPKLIC; DATAUZLU:TYPDATA);
{ procedura vloží do stromu prvek s klíčem K a se složkou DATAUZLU }
begin
	if KOREN = nil
		then	{ Prvek s klíčem K není prvkem stromu; vloží se nový prvek }
			begin
				new (KOREN);
				with KOREN^ do begin
{ Ustavení hodnoty, klíče a ukazatelů nového uzlu }
	KLIC := K;
	LEVY := ni;‘
	PRAVY := ni;
	DATA := DATAUZLU;
end
				end
			else	{ Zatím se hledaný uzel nenašel a ještě se nedošlo k listu }
				if K < KOREN^.KLIC
					then	{ Pokračuj v levém podstromu }
						INSERT (KOREN^.LEVY, K, DATAUZLU)
					else
						if K > KOREN^.KLIC
						then	{ Pokračuj v pravém podstromu }
							INSERT (KOREN^.PRAVY, K, DATAUZLU)
						else	{ Uzel s klíčem K je prvkem stromu,
							  jeho datová složka se přepíše }
							KOREN^.DATA := DATAUZLU
	end 	{ provedury INSERT }
	
 

3.2.2. Nerekurzivní zápis operace INSERT

Nerekurzivní zápis procedury INSERT je podstatně delší a vyžaduje samostatný mechanismus vyhledání.

procedure INSERT (var KOREN:TYPUKUZEL; k:TYPKLIC; DATAUZLU:TYPDATA);
var POMUK, KDE:TYPUKUZEL;	{ Pomocné proměnné pro příkaz new a pro 
  lokalizaci místa vkládání }
 	     NASEL:Boolean;	{ Řídící proměnná cyklu }
	
	procedure INSERTSEARCH (KOREN:TYPUKUZEL; K:TYPKLIC; var NASEL:
				         Boolean; var KDE:TYPUKUZEL);
	{ Tělo procedury bude rozvedeno později. Procedura vyhledává v BVS prvek
	  s klíčem K. Nelezne-li jej, pak NASEL=true a KDE zpřístupňuje nalezený prvek.
	  Jinak je NASEL=false a KDE zpřístupňuje list, na který se připojí nový uzel. }

begin	{ Začátek těla procedury INSERT }
	INSERTSEARCH (KOREN, K, NASEL, KDE);	{ Vyhledání }
	if NASEL
		then KDE^.DATA := DATAUZLU { Přepis datové složky nalezeného uzlu }
		else { Prvek nebyl nalezen, bude se vkládat nový uzel }
			begin
				new (POMUK);
				with POMUK^ do { Ustavení hodnot složek nového uzlu }
					begin
						DATA := DATAUZLU;
						KLIC := K;
						LEVY := nil;
						PRAVY := nil;
					end;
				if KDE = nil
					then KOREN := POMUK { Strom byl prázdný; nový 
    uzel se stane kořenem }
					else { Strom byl neprázdný, uzel se připojí k listu }
						if KDE^.KLIC > K
							then KDE^.LEVY := POMUK
							{ Připojení uzlu k listu vlevo }
							else KDE^.PRAVY := POMUK
							{ Připojení uzlu k listu vpravo }
			end { příkazu if NASEL }
end; { procedury INSERT }

Procedura vyhledávání za účelem vkládání uzlu má tvar:

procedure INSERTSEARCH (KOREN:TYPUKUZEL; K:TYPKLIC; var NASEL:Boolean;
			         var KDE:TYPUKUZEL);
var KONEC:Boolean;	{ Pomocná proměnná pro řízení cyklu }
begin
	NASEL := false;
	if KOREN = nil
	then 	{ Strom je prázdný }
		KDE := nil
	else	{ Strom je neprázdný }
		begin
			KONEC := false;
			while not KONEC do
			begin
				KDE := KOREN
				if KOREN^.KLIC = K
				then { Úspěšné vyhledání }
					begin
						NASEL := true
						KONEC := true
					end
				else begin
					if KOREN^.KLIC > K
					then KOREN := KOREN^.LEVY
					else KOREN := KOREN^.PRAVY;
					KONEC := KOREN = nil;
				        end
			end { cyklu while }
		end
end { procedury INSERTSEARCH }

3.3. Rušení prvku v BVS - operace DELETE

U všech předcházejících implementačních metod ATD tabulka bylo vždy rušení prvku v tabulce obtižnější než vkládání. Binární vyhledávací strom je typický svou vhodností pro implementaci dynamické tabulky. Přesto je vyřazování uzlu ze stromu (operace DELETE) složitější, než vkládání nového uzlu (operace INSERT). Jeden z možných postupů při vyřazování uzlu, na němž je „levá“ a „pravá“ varianta rušení uzlů.

Mechanizmus tohoto způsobu rušení lze popsat slovně takto:

Rušíme-li neterminální uzel, který má „synovské uzly“, pak levý synovský uzel připojíme k nadřazenému (praotcovskému) uzlu místo rušeného (otcovského) uzlu a pravý synovský uzel připojíme k nejpravějšímu listu podstromu levého synovského uzlu (tzv. „levá“ varianta) nebo provedeme stranově sdruženou variantu („pravá“ varianta). Je-li levý nebo pravý synovský prázdný, pak se situace zjednodušší: na místo rušeného otcovského uzlu se připojí neprázdný synovský podstrom. Ruší-li se kořen, stane se kořenem levý (resp. pravý) synovský uzel a pravý (resp. levý) podstrom se připojí k nejpravějšímu (resp. nejlevějšímu) listu levého (resp. pravého) podstromu. Vyřazovaný prvek se zruší operací typu DISPOSE.

Vážnou nevýhodou tohoto řešení je skutečnost, že rušením uzlů (zvláště těch, které jsou blízko kořenu) se zvyšuje počet úrovní (výška) stromu. Tím se prodlužuje cesta k listům stromu, a tudíž i proces vyhledávání. Nebudeme proto tuto metodu dále rozvíjet. Z cvičných důvodů lze doporučit vytvoření procedury DELETE pracující podle této metody.

Výhodnější řešení nabízí mechanismus, vycházející z této úvahy: rušení listu a uzlu, jehož jeden z podstromů je prázdný, je velmi jednoduché. Položme si otázku, zda existuje list nebo uzel jen s jedním synem, jehož hodnotu lze vložit do rušeného uzlu (přepsat hodnotu rušeného uzlu), takový, že strom, který vznikne tímto přepisem a zrušením takového listu (nebo uzlu jen s jedním synem), splňuje podmínky BVS? Takovým uzlem je nejpravější uzel levého podstromu „rušeného“ uzlu. I zde lze vytvořit stranově souměrnou variantu „nejlevějšího uzlu pravého podstromu“.

3.3.1. Rekurzivní zápis operace INSERT

Rekurzivní zápis operace DELETE je, podobně jako v předcházejícím případech, kratší a elegantnější než jeho nerekurzivní podoba. Rekurzivní zápis je však obtížnější a nelze očekávat, že by takový algoritmus samostatně vytvořil nezkušený programátor.

procedura DELETE (var KOREN:TYPUKUZEL; K:TYPKLIC);
{ Procedura DELETE vyhledá ve stromu zadaném ukazatelem na kořen (KOREN) uzel s klíčem K a zruší tento uzel druhou z metod uvedených v předcházejícím odstavci . Nenajde-li se uzel s klíčem K, neprovede procedura žádné změny nad stromem a na tuto situaci dále nereaguje. Případnou reakci lze vložit na komentářem vyznačené místo. }
var POMUK:TYPUKUZEL;	{ Pomocný ukazatel na rušený uzel }

procedura DEL (var UK:TYPUKUZEL);
{ Pomocná procedura DEL prochází po nejpravější větvi levého podstromu vyřazovaného uzlu (POMUK) a hledá nejpravější uzel (UK). Po jeho nalezení přepíše jeho hodnotu datovou složkou a klíč uzlu POMUK a uvolní uzel UK tak, aby po skončení procedury mohl být zrušen příkazem dispose. }
begin
	if UK^.PRAVY <> nil
	then DEL (UK^.PRAVY)	{ hledá dále v pravém podstromu }
	else	{ Nalezl nejpravější, provede přepis a uvolnění uzlu UK }
		begin
			POMUK^.KLIC := UK^.KLIC;	{ Přepis složky KLIC }
			POMUK^.DATA := UK^.DATA;	{ Přepis složky DATA }
			POMUK := UK;
			UK := UK^.LEVY;	{ Uvolnění uzlu UK^. Pozor! UK je
			v proceduře DEL ukazatelová složka nadřazeného uzlu
			k uzlu UK^ }
		end
end;	{ Pomocné procedury DEL }

	begin { Začátek procedury DELETE }
	if KOREN <> nil
	then { Hledání není u konce; hledaný prvek ještě může být ve stromu }
		if K < KOREN^.KLIC
		then DELETE (KOREN^.LEVY, K)	{ Hledej v levem podstromu }
		else if K < KOREN^.KLIC
			then DELETE (KOREN^.PRAVY, K)	{ Hledej v pravém podstromu }
			else { hodnota uzlu KOREN^ se ruší }
				begin
					POMUK := KOREN;
					if POMUK^.PRAVY = nil
					then { Nemá pravý podstrom; uvolní se tím, že se levý
						podstrom připojí na nadřazený uzel. }
						KOREN := POMUK^.LEVY
					else { Má pravý podstrom; uzel se bude přepisovat
						nejpravějším v levém podstromu procedurou
						DEL,  je-li levý strom neprázdný, připojí se 
pravý podstrom na nadřazený uzel. }
if POMUK^.LEVY = nil
then KOREN := POMUK^.PRAVY;
	{ Připojení pravého podstromu }
else DEL (POMUK^.LEVY);
						dispose (POMUK)	{ Zrušení uvolněného uzlu }
					end { za else na tomto místě lze reagovat na nenalezení prvku
						ve stromu }
	end { Procedury DELETE }