Implementació d'un arbre de cerca binari

2024 Autora: Angel Austin | [email protected]. Última modificació: 2023-12-17 05:19

Arbre de cerca binari: una base de dades estructurada que conté nodes, dos enllaços a altres nodes, dret i esquerre. Els nodes són un objecte de la classe que té dades i NULL és el signe que marca el final de l'arbre.

Sovint s'anomena BST, que té una propietat especial: els nodes més grans que l'arrel se situen a la seva dreta i els més petits a l'esquerra.

Teoria general i terminologia

En un arbre de cerca binari, cada node, excloent l'arrel, està connectat per una vora dirigida d'un node a un altre, que s'anomena pare. Cadascun d'ells es pot connectar a un nombre arbitrari de nodes, anomenats fills. Els nodes sense "fills" s'anomenen fulles (nodes exteriors). Els elements que no són fulles s'anomenen interns. Els nodes amb el mateix pare són germans. El node superior s'anomena arrel. A BST, assigneu un element a cada node i assegureu-vos que tinguin una propietat especial establerta per a ells.

Terminologia de l'arbre:

La profunditat d'un node és el nombre d'arestes definides des de l'arrel fins a aquest.
L'alçada d'un node és el nombre d'ares definides des d'aquest fins a la fulla més profunda.
L'alçada de l'arbre ve determinada per l'alçada de l'arrel.
L'arbre de cerca binària és un disseny especial, ofereix la millor relació entre alçada i nombre de nodes.
Alçada h amb N nodes com a màxim O (log N).

Podeu demostrar-ho fàcilment comptant els nodes a cada nivell, començant per l'arrel, suposant que conté el major nombre d'ells: n=1 + 2 + 4 + … + 2 h-1 + 2 h=2 h + 1 - 1 La resolució d'això per a h dóna h=O (log n).

Avantatges de la fusta:

Reflecteix les relacions estructurals de les dades.
S'utilitza per representar jerarquies.
Garantir una instal·lació i cerca eficients.
Els arbres són dades molt flexibles, que us permeten moure subarbres amb el mínim esforç.

Mètode de cerca

En general, per determinar si un valor és a la BST, inicieu un arbre de cerca binari a la seva arrel i determineu si compleix els requisits:

estar a l'arrel;
estar al subarbre esquerre de l'arrel;
al subarbre dret de l'arrel.

Si no es compleix cap registre base, es realitza una cerca recursiva al subarbre corresponent. En realitat, hi ha dues opcions bàsiques:

L'arbre està buit; retorna fals.
El valor és al node arrel; retorna true.

S'ha de tenir en compte que un arbre de cerca binari amb un esquema desenvolupat sempre comença a cercar al llarg del camí des de l'arrel fins a la fulla. En el pitjor dels casos, arriba fins a la fulla. Per tant, el pitjor temps és proporcional a la longitud del camí més llarg des de l'arrel fins a la fulla, que és l'alçada de l'arbre. En general, és quan cal saber quant de temps es triga a buscar en funció del nombre de valors emmagatzemats a l'arbre.

En altres paraules, hi ha una relació entre el nombre de nodes d'un BST i l'alçada d'un arbre, depenent de la seva "forma". En el pitjor dels casos, els nodes només tenen un fill, i un arbre de cerca binari equilibrat és essencialment una llista enllaçada. Per exemple:

Aquest arbre té 5 nodes i alçada=5. Trobar valors en el rang 16-19 i 21-29 requerirà el següent camí des de l'arrel fins a la fulla (el node que conté el valor 20), és a dir., trigarà un temps proporcional al nombre de nodes. En el millor dels casos, tots tenen 2 fills i les fulles es troben a la mateixa profunditat.

Aquest arbre de cerca binari té 7 nodes i alçada=3. En general, un arbre com aquest (arbre complet) tindrà una alçada d'aproximadament log 2 (N), on N és el nombre de nodes de l'arbre.. El valor de log 2 (N) és el nombre de vegades (2) que N es pot dividir abans que s'arribi a zero.

Resum: el pitjor moment necessari per cercar a BST és O (alçada de l'arbre). L'arbre "lineal" del pitjor cas és O(N), on N és el nombre de nodes de l'arbre. En el millor dels casos, un arbre "complet" és O(log N).

inserció binària BST

Em pregunto on hauria de serel nou node es troba al BST, cal entendre la lògica, s'ha de col·locar on el trobi l'usuari. A més, cal recordar les regles:

No es permeten duplicats, si intenteu inserir un valor duplicat es generarà una excepció.
El mètode d'inserció pública utilitza un mètode d'ajuda recursiu "d'ajuda" per inserir realment.
Un node que conté un valor nou s'insereix sempre com a full a BST.
El mètode d'inserció públic retorna void, però el mètode auxiliar retorna un BSTnode. Ho fa per gestionar el cas en què el node que se li passa sigui nul.

En general, el mètode d'ajuda indica que si l'arbre de cerca binari original està buit, el resultat és un arbre amb un node. En cas contrari, el resultat serà un punter al mateix node que s'ha passat com a argument.

Supressió a l'algorisme binari

Com és d'esperar, suprimir un element implica trobar un node que contingui el valor que cal eliminar. Hi ha diverses coses en aquest codi:

BST utilitza un mètode d'eliminació sobrecarregat i auxiliar. Si l'element que busqueu no es troba a l'arbre, el mètode d'ajuda s'anomenarà finalment amb n==nul. Això no es considera un error, l'arbre simplement no canvia en aquest cas. El mètode d'ajuda d'eliminació retorna un valor: un punter a l'arbre actualitzat.
Quan s'elimina una fulla, l'eliminació de l'arbre de cerca binari estableix el punter secundari corresponent del seu pare a nul, o l'arrel a nul si el que s'elimina ésel node és una arrel i no té fills.
Tingueu en compte que la trucada de supressió ha de ser una de les següents: root=suprimir (arrel, clau), n.setLeft (suprimir (n.getLeft (), clau)), n.setRight (suprimir (n. getRight(), clau)). Per tant, en els tres casos és correcte que el mètode d'eliminació simplement retorni null.
Quan la cerca del node que conté el valor que s'ha d'esborrar té èxit, hi ha tres opcions: el node que s'ha d'esborrar és una fulla (no té fills), el node que s'ha d'esborrar té un fill, en té dos. nens.
Quan el node que s'elimina té un fill, simplement podeu substituir-lo per un fill, retornant un punter al fill.
Si el node que s'ha de suprimir té zero o 1 fill, el mètode de supressió "seguirà el camí" des de l'arrel fins a aquest node. Per tant, el pitjor moment és proporcional a l'alçada de l'arbre, tant per a la cerca com per a la inserció.

Si el node que s'ha d'eliminar té dos fills, es segueixen els passos següents:

Cerca el node que vols suprimir, seguint el camí des de l'arrel fins a aquest.
Cerca el valor més petit de v al subarbre dret, continuant pel camí cap a la fulla.
Elimineu recursivament el valor de v, seguiu el mateix camí que al pas 2.
Així, en el pitjor dels casos, el camí des de l'arrel fins a la fulla es realitza dues vegades.

Ordre de travessa

Traversal és un procés que visita tots els nodes d'un arbre. Com que un arbre de cerca binari C és una estructura de dades no lineal, no hi ha cap recorregut únic. Per exemple, de vegades diversos algorismes de recorregutagrupats en els dos tipus següents:

profunditat d'encreuament;
primera passada.

Només hi ha un tipus de creuament d'amplada: eludir el nivell. Aquest recorregut visita els nodes de nivell avall i esquerre, superior i dret.

Hi ha tres tipus diferents de creuaments de profunditat:

Passa la comanda prèvia: primer visiteu els pares i després el fill esquerre i dret.
Passing InOrder: visita al fill esquerre, després al pare i al fill dret.
Passat la comanda postal: visitar el fill esquerre, després el fill dret i després el pare.

Exemple de quatre recorreguts d'un arbre de cerca binari:

Preordena: 8, 5, 9, 7, 1, 12, 2, 4, 11, 3.
En ordre - 9, 5, 1, 7, 2, 12, 8, 4, 3, 11.
PostOrder - 9, 1, 2, 12, 7, 5, 3, 11, 4, 8.
LevelOrder - 8, 5, 4, 9, 7, 11, 1, 12, 3, 2.

La figura mostra l'ordre en què es visiten els nodes. El número 1 és el primer node d'un recorregut concret i el 7 és l'últim node.

Aquests recorreguts generals es poden representar com un únic algorisme, suposant que cada node es visita tres vegades. El recorregut Euler és un passeig al voltant d'un arbre binari on cada vora es tracta com una paret que l'usuari no pot creuar. En aquesta caminada, cada node es visitarà a l'esquerra, a sota o a la dreta. El recorregut d'Euler, que visita els nodes de l'esquerra, fa que la preposició es s alta. Quan es visiten els nodes de sota, es recorren en ordre. I quan es visiten els nodes de la dreta, obteniubypass pas a pas.

Navegació i depuració

Per facilitar la navegació per l'arbre, creeu funcions que primer comprovin si són el fill esquerre o dret. Per canviar la posició d'un node, ha d'haver un accés fàcil al punter al node pare. Implementar correctament un arbre és molt difícil, així que cal conèixer i aplicar els processos de depuració. Un arbre de cerca binari amb una implementació sovint té punters que en realitat no indiquen la direcció del viatge.

Per esbrinar-ho tot, s'utilitza una funció que verifica si l'arbre pot ser correcte i ajuda a trobar molts errors. Per exemple, comprova si el node pare és un node fill. Amb assert(is_wellformed(root)) molts errors es poden detectar prematurament. Utilitzant un parell de punts d'interrupció determinats dins d'aquesta funció, també podeu determinar exactament quin punter és incorrecte.

Funció Konsolenausgabe

Aquesta funció envia tot l'arbre a la consola i, per tant, és molt útil. L'ordre en què s'executa l'objectiu de sortida de l'arbre és:

Per fer-ho, primer heu de determinar quina informació sortirà a través del node.
I també has de saber l'ample i l' alt que és l'arbre per tenir en compte quant d'espai deixar.
Les funcions següents calculen aquesta informació per a l'arbre i cada subarbre. Com que només podeu escriure a la consola línia per línia, també haureu d'imprimir l'arbre línia per línia.
Ara necessitem una altra manera de retirar-nostot l'arbre, no només línia per línia.
Amb l'ajuda de la funció d'abocat, podeu llegir l'arbre i millorar significativament l'algoritme de sortida, pel que fa a la velocitat.

No obstant això, aquesta funció serà difícil d'utilitzar en arbres grans.

Còpia constructor i destructor

Com que un arbre no és una estructura de dades trivial, és millor implementar un constructor de còpia, un destructor i un operador d'assignació. El destructor és fàcil d'implementar de forma recursiva. Per als arbres molt grans, pot gestionar el "desbordament de pila". En aquest cas, es formula de manera iterativa. La idea és eliminar la fulla que representa el valor més petit de totes les fulles, de manera que quedi al costat esquerre de l'arbre. Tallar les primeres fulles en crea de noves i l'arbre s'encongeix fins que finalment deixa d'existir.

El constructor de còpies també es pot implementar de forma recursiva, però aneu amb compte si es llança una excepció. En cas contrari, l'arbre es torna ràpidament confús i propens a errors. És per això que es prefereix la versió iterativa. La idea és passar per l'arbre vell i l'arbre nou, com ho faries al destructor, clonant tots els nodes que hi ha a l'arbre vell però no els nous.

Amb aquest mètode, la implementació de l'arbre de cerca binari sempre està en un estat saludable i el destructor pot eliminar-la fins i tot en un estat incomplet. Si es produeix una excepció, tot el que heu de fer és indicar al destructor que esborri l'arbre semielaborat. operador d'assignacióes pot implementar fàcilment mitjançant Còpia i intercanvi.

Creació d'un arbre de cerca binari

Els arbres de cerca binaris òptims són increïblement eficients si es gestionen correctament. Algunes regles per als arbres de cerca binaris:

Un node principal té com a màxim 2 nodes secundaris.
El node secundari esquerre sempre és menor que el node pare.
Un node fill vàlid sempre és més gran o igual que el node pare.

La matriu que s'utilitzarà per construir l'arbre de cerca binari:

Una matriu d'enters base de set valors en ordre no ordenat.
El primer valor de la matriu és 10, de manera que el primer pas per construir l'arbre és crear un node arrel de 10, tal com es mostra aquí.
Amb un conjunt de nodes arrel, tots els altres valors seran fills d'aquest node. En referència a les regles, el primer pas que cal fer per afegir 7 a l'arbre és comparar-lo amb el node arrel.
Si el valor 7 és inferior a 10, es convertirà en el node secundari esquerre.
Si el valor 7 és superior o igual a 10, es mourà cap a la dreta. Com que se sap que 7 és inferior a 10, es designa com el node secundari esquerre.
Recorreu recursivament comparacions per a cada element.
Seguint el mateix patró, feu la mateixa comparació amb el valor 14 de la matriu.
Comparant el valor 14 amb el node arrel 10, sabent que 14 és el fill correcte.
Passejant per la matriu,arriba a 20.
Comenceu comparant la matriu amb 10, el que sigui més gran. Així que moveu-vos cap a la dreta i compareu-lo amb 14 anys, té més de 14 anys i no té cap fill a la dreta.
Ara hi ha un valor d'1. Seguint el mateix patró que els altres valors, compareu 1 amb 10, moveu-vos cap a l'esquerra i compareu amb 7 i finalment amb l'1 fill esquerre del 7è node.
Si el valor és 5, compareu-lo amb 10. Com que 5 és menor que 10, passeu a l'esquerra i compareu-lo amb 7.
Sabent que 5 és menys de 7, continua per l'arbre i compara 5 amb 1 valor.
Si 1 no té fills i 5 és més gran que 1, aleshores 5 és un fill vàlid d'1 node.
Per fi inseriu el valor 8 a l'arbre.
Quan 8 sigui menys de 10, moveu-lo cap a l'esquerra i compareu-lo amb 7, 8 és més gran que 7, així que moveu-lo cap a la dreta i completa l'arbre, fent que 8 sigui un fill adequat de 7.

Aconseguir i avaluar la senzilla elegància dels arbres de cerca binaris òptims. Com molts temes de programació, el poder dels arbres de cerca binaris prové de la seva capacitat per resoldre dades en components petits i relacionats. A partir d'ara, podeu treballar amb el conjunt de dades complet de manera organitzada.

Problemes potencials de cerca binària

Els arbres de cerca binaris són fantàstics, però cal tenir en compte algunes advertències. Normalment només són efectius si estan equilibrats. Un arbre equilibrat és un arbre en el qualla diferència entre les altures dels subarbres de qualsevol node de l'arbre és com a màxim una. Vegem un exemple que pot ajudar a aclarir les regles. Imaginem que la matriu comença com a ordenable.

Si intenteu executar un algorisme d'arbre de cerca binari en aquest arbre, funcionarà exactament com si estigués iterant per la matriu fins que es trobi el valor desitjat. El poder de la cerca binària rau en la capacitat de filtrar ràpidament els valors no desitjats. Quan un arbre no està equilibrat, no oferirà els mateixos beneficis que un arbre equilibrat.

És molt important examinar les dades amb què treballa l'usuari quan es crea un arbre de cerca binari. Podeu integrar rutines com ara l'aleatorització de matrius abans d'implementar un arbre de cerca binari per a nombres enters per equilibrar-lo.

Exemples de càlcul de cerca binària

Hem de determinar quin tipus d'arbre resultarà si s'insereix 25 a l'arbre de cerca binari següent:

5 15

/ /

2 12 20

Quan s'insereix x en un arbre T que encara no conté x, la clau x sempre es col·loca en una fulla nova. En relació amb això, el nou arbre tindrà aquest aspecte:

5 15

/ /

2 12 20

Quin tipus d'arbre obtindríeu si inseriu 7 a l'arbre de cerca binari següent?

5 15

/ /

2 12 20

Resposta:

5 15

/ / /

2 7 12 20

Un arbre de cerca binari es pot utilitzar per emmagatzemar qualsevol objecte. L'avantatge d'utilitzar un arbre de cerca binari en lloc d'una llista enllaçada és que si l'arbre està raonablement equilibrat i més semblant a un arbre "ple" que a un "lineal", es poden implementar totes les operacions d'inserció, cerca i supressió per executar-les. O (log N) temps.