Aurreskua
Artikulu hau bilaketa-zuhaitz bitarrei buruzkoa da. Duela gutxi artikulu bat idatzi dut
Zuhaitz bat ertz bidez konektatutako nodoz osatutako datu-egitura da. Zuhaitza grafiko baten kasu berezi bat dela esan dezakegu. Hona hemen zuhaitz adibide bat:
Hau ez da bilaketa-zuhaitz bitar bat! Dena mozketa azpian dago!
terminologia
erro
Zuhaitz sustraia goiko nodoa da. Adibidean, hau A nodoa da. Zuhaitzean, bide bakarrak eraman dezake errotik beste edozein nodora! Izan ere, edozein nodo har daiteke nodo honi dagokion azpizuhaitzaren errotzat.
Gurasoak/seme-alabak
Nodo guztiek erroa izan ezik beste nodo batera doan ertz bat dute. Uneko nodoaren gaineko nodoari deitzen zaio gurasoa nodo hau. Unekoaren azpian dagoen eta hari konektatuta dagoen nodo bati deitzen zaio ondorengoa nodo hau. Har dezagun adibide bat. Hartu B nodoa, orduan bere gurasoa A nodoa izango da eta bere seme-alabak D, E eta F nodoak izango dira.
xafla
Seme-alabarik ez duen nodoari zuhaitzaren hosto deitzen zaio. Adibidean, D, E, F, G, I, J, K nodoak hostoak izango dira.
Hau da oinarrizko terminologia. Beste kontzeptu batzuk geroago eztabaidatuko dira. Beraz, zuhaitz bitarra nodo bakoitzak bi seme-alaba baino gehiago izango dituen zuhaitza da. Asmatu duzun bezala, adibideko zuhaitza ez da bitarra izango, B eta H nodoek bi seme baino gehiago dituztelako. Hona hemen zuhaitz bitar baten adibide bat:
Zuhaitzaren nodoek edozein informazio eduki dezakete. Bilaketa-zuhaitz bitarra propietate hauek dituen zuhaitz bitarra da:
- Ezkerreko eta eskuineko azpizuhaitzak bilaketa-zuhaitz bitarrak dira.
- X nodo arbitrario baten ezkerreko azpizuhaitzaren nodo guztiek X nodoaren datu-gakoaren balioak baino txikiagoak dituzte.
- X nodo arbitrario baten eskuineko azpizuhaitzaren nodo guztiek X nodoaren datu-gakoaren balio handiagoak edo berdinak dituzte.
gakoa - nodoaren ezaugarri batzuk (adibidez, zenbaki bat). Gakoa beharrezkoa da gako horri dagokion zuhaitzaren elementua aurkitu ahal izateko. Bilaketa-zuhaitz bitar adibidea:
zuhaitz ikuspegia
Aurrera doan heinean, kode zati batzuk (baliteke osatu gabeak) sartuko ditut zure ulermena hobetzeko. Kode osoa artikuluaren amaieran egongo da.
Zuhaitza nodoz osatuta dago. Nodoen egitura:
public class Node<T> {
private T data;
private int key;
private Node<T> leftChild;
private Node<T> rightChild;
public Node(T data, int key) {
this.data = data;
this.key = key;
}
public Node<T> getLeftChild() {
return leftChild;
}
public Node<T> getRightChild() {
return rightChild;
}
//...ΠΎΡΡΠ°Π»ΡΠ½ΡΠ΅ ΠΌΠ΅ΡΠΎΠ΄Ρ ΡΠ·Π»Π°
}
Nodo bakoitzak bi seme-alaba ditu (oso posible da leftChild eta/edo rightChild seme-alabak nuluak izatea). Seguruenik ulertu zenuen kasu honetan zenbaki-datuak nodoan gordetako datuak direla; tekla - nodo-gakoa.
Korapiloa asmatu genuen, orain hitz egin dezagun zuhaitzen arazo larriei buruz. Hemen eta behean, "zuhaitza" hitzak bilaketa-zuhaitz bitar baten kontzeptua esan nahi du. Zuhaitz egitura bitarra:
public class BinaryTree<T> {
private Node<T> root;
//ΠΌΠ΅ΡΠΎΠ΄Ρ Π΄Π΅ΡΠ΅Π²Π°
}
Klase-eremu gisa, zuhaitzaren erroa besterik ez dugu behar, errotik, getLeftChild() eta getRightChild() metodoak erabiliz, zuhaitzaren edozein nodotara irits zaitezke.
Zuhaitz algoritmoak
bilaketa
Demagun zuhaitz eraikia duzula. Nola aurkitu elementua gako-gakoarekin? Errotik zuhaitzean behera sekuentzialki mugitu eta gakoaren balioa hurrengo nodoko gakoarekin alderatu behar duzu: gakoa hurrengo nodoaren gakoa baino txikiagoa bada, joan nodoaren ezkerreko ondorengora, gehiago bada - eskuinera, teklak berdinak badira - nahi den nodoa aurkitzen da! Kode garrantzitsua:
public Node<T> find(int key) {
Node<T> current = root;
while (current.getKey() != key) {
if (key < current.getKey())
current = current.getLeftChild();
else
current = current.getRightChild();
if (current == null)
return null;
}
return current;
}
Korrontea nulu bihurtzen bada, orduan iterazioa zuhaitzaren amaierara iritsi da (kontzeptu mailan, zuhaitzean existitzen ez den leku batean zaude - hosto baten seme-alaba).
Demagun bilaketa-algoritmoaren eraginkortasuna zuhaitz orekatu batean (nodoak berdin-berdin banatuta dauden zuhaitza). Orduan bilaketa-eraginkortasuna O(log(n)) izango da, eta 2 oinarriko logaritmoa. Ikus: zuhaitz orekatu batean n elementu badaude, horrek esan nahi du zuhaitzaren log(n) oinarri 2 mailak egongo direla. Eta bilaketan, zikloko urrats bat, maila bat jaisten zara.
txertatzeko
Bilaketaren funtsa ulertu baduzu, ez zaizu zaila izango txertaketa ulertzea. Zuhaitzaren hostora jaitsi besterik ez duzu behar (bilaketan deskribatutako jaitsiera-arauen arabera) eta haren ondorengo bihurtu - ezkerrera edo eskuinera, gakoaren arabera. Ezarpena:
public void insert(T insertData, int key) {
Node<T> current = root;
Node<T> parent;
Node<T> newNode = new Node<>(insertData, key);
if (root == null)
root = newNode;
else {
while (true) {
parent = current;
if (key < current.getKey()) {
current = current.getLeftChild();
if (current == null) {
parent.setLeftChild(newNode);
return;
}
}
else {
current = current.getRightChild();
if (current == null) {
parent.setRightChild(newNode);
return;
}
}
}
}
}
Kasu honetan, uneko nodoaz gain, beharrezkoa da uneko nodoaren gurasoari buruzko informazioa gordetzea. Korrontea nulu bihurtzen denean, aldagai nagusiak behar dugun orria izango du.
Txertatzeko eraginkortasuna bilaketaren berdina izango da, jakina - O(log(n)).
kentzea
Ezabatzea da zuhaitz batekin egin beharko den eragiketarik konplexuena. Argi dago lehenik eta behin kenduko dugun elementua bilatu beharko dela. Baina orduan zer? Bere erreferentzia nulu gisa ezartzen badugu, orduan nodo hau erroa duen azpizuhaitzari buruzko informazioa galduko dugu. Zuhaitzak kentzeko metodoak hiru kasutan banatzen dira.
Lehenengo kasua. Kendu beharreko nodoak ez du seme-alabarik.
Ezabatu beharreko nodoak seme-alabarik ez badu, hosto bat dela esan nahi du. Hori dela eta, bere gurasoaren leftChild edo rightChild eremuak nulu gisa ezar ditzakezu.
Bigarren kasua. Kendu beharreko nodoak seme-alaba bat du
Kasu hau ere ez da oso zaila. Itzul gaitezen gure adibidera. Demagun 14 gakoa duen elementu bat ezabatu behar dugula. Onartu 10 gakoa duen nodo baten seme-alaba egokia denez, bere ondorengo edozeinek (kasu honetan, eskuinekoa) 10 baino gako handiagoa izango duela, beraz erraz "moztu" daiteke zuhaitzetik, eta gurasoa zuzenean ezabatzen ari den nodoaren haurra konektatu, hau da. konektatu 10. gakoa duen nodoa 13. nodoarekin. Egoera antzekoa izango litzateke bere gurasoaren ezkerreko seme-alaba den nodo bat ezabatu beharko bagenu. Pentsa ezazu zeure burua - analogia zehatza.
Hirugarren kasua. Nodok bi seme ditu
Kasurik zailena. Ikus dezagun adibide berri bati.
Bilatu oinordeko bat
Demagun gakoarekin nodoa kendu behar dugula 25. Nor jarriko dugu haren lekuan? Bere jarraitzaileetako batek (ondorengoak edo ondorengoen ondorengoak) bihurtu behar du ondorengoa(kendutako nodoaren lekua hartuko duena).
Nola dakizu nor izan behar duen ondorengoa? Intuitiboki, zuhaitzeko nodoa da, zeinaren gakoa kentzen ari den nodotik hurrengo handiena den. Algoritmoa honakoa da. Bere eskuineko haurra joan behar duzu (beti eskuinera, lehendik ere esana baitzen ondorengoaren gakoa ezabatzen ari den nodoaren gakoa baino handiagoa dela), eta ondoren eskuin honen ezkerreko seme-alaben katetik pasa. ume. Adibidean, 35 gakoa duen nodora joan behar dugu, eta, ondoren, bere ezkerreko seme-alaben katetik behera jaitsi hostora - kasu honetan, kate hau 30 gakoa duen nodoaz osatuta dago soilik. Zorrotz esanda, bilatzen ari gara. nahi den nodoa baino handiagoa den nodo multzoko nodo txikiena.
Ondorengo bilaketa metodoaren kodea:
public Node<T> getSuccessor(Node<T> deleteNode) {
Node<T> parentSuccessor = deleteNode;//ΡΠΎΠ΄ΠΈΡΠ΅Π»Ρ ΠΏΡΠ΅Π΅ΠΌΠ½ΠΈΠΊΠ°
Node<T> successor = deleteNode;//ΠΏΡΠ΅Π΅ΠΌΠ½ΠΈΠΊ
Node<T> current = successor.getRightChild();//ΠΏΡΠΎΡΡΠΎ "ΠΏΡΠΎΠ±Π΅Π³Π°ΡΡΠΈΠΉ" ΡΠ·Π΅Π»
while (current != null) {
parentSuccessor = successor;
successor = current;
current = current.getLeftChild();
}
//Π½Π° Π²ΡΡ
ΠΎΠ΄Π΅ ΠΈΠ· ΡΠΈΠΊΠ»Π° ΠΈΠΌΠ΅Π΅ΠΌ ΠΏΡΠ΅Π΅ΠΌΠ½ΠΈΠΊΠ° ΠΈ ΡΠΎΠ΄ΠΈΡΠ΅Π»Ρ ΠΏΡΠ΅Π΅ΠΌΠ½ΠΈΠΊΠ°
if (successor != deleteNode.getRightChild()) {//Π΅ΡΠ»ΠΈ ΠΏΡΠ΅Π΅ΠΌΠ½ΠΈΠΊ Π½Π΅ ΡΠΎΠ²ΠΏΠ°Π΄Π°Π΅Ρ Ρ ΠΏΡΠ°Π²ΡΠΌ ΠΏΠΎΡΠΎΠΌΠΊΠΎΠΌ ΡΠ΄Π°Π»ΡΠ΅ΠΌΠΎΠ³ΠΎ ΡΠ·Π»Π°
parentSuccessor.setLeftChild(successor.getRightChild());//ΡΠΎ Π΅Π³ΠΎ ΡΠΎΠ΄ΠΈΡΠ΅Π»Ρ Π·Π°Π±ΠΈΡΠ°Π΅Ρ ΡΠ΅Π±Π΅ ΠΏΠΎΡΠΎΠΌΠΊΠ° ΠΏΡΠ΅Π΅ΠΌΠ½ΠΈΠΊΠ°, ΡΡΠΎΠ±Ρ Π½Π΅ ΠΏΠΎΡΠ΅ΡΡΡΡ Π΅Π³ΠΎ
successor.setRightChild(deleteNode.getRightChild());//ΡΠ²ΡΠ·ΡΠ²Π°Π΅ΠΌ ΠΏΡΠ΅Π΅ΠΌΠ½ΠΈΠΊΠ° Ρ ΠΏΡΠ°Π²ΡΠΌ ΠΏΠΎΡΠΎΠΌΠΊΠΎΠΌ ΡΠ΄Π°Π»ΡΠ΅ΠΌΠΎΠ³ΠΎ ΡΠ·Π»Π°
}
return successor;
}
Ezabatzeko metodoaren kode osoa:
public boolean delete(int deleteKey) {
Node<T> current = root;
Node<T> parent = current;
boolean isLeftChild = false;//Π Π·Π°Π²ΠΈΡΠΈΠΌΠΎΡΡΠΈ ΠΎΡ ΡΠΎΠ³ΠΎ, ΡΠ²Π»ΡΠ΅ΡΡΡ Π»ΠΈ ΡΠ΄Π°Π»ΡΠ΅ΠΌΡΠΉ ΡΠ·Π΅Π» Π»Π΅Π²ΡΠΌ ΠΈΠ»ΠΈ ΠΏΡΠ°Π²ΡΠΌ ΠΏΠΎΡΠΎΠΌΠΊΠΎΠΌ ΡΠ²ΠΎΠ΅Π³ΠΎ ΡΠΎΠ΄ΠΈΡΠ΅Π»Ρ, Π±ΡΠ»Π΅Π²ΡΠΊΠ°Ρ ΠΏΠ΅ΡΠ΅ΠΌΠ΅Π½Π½Π°Ρ isLeftChild Π±ΡΠ΄Π΅Ρ ΠΏΡΠΈΠ½ΠΈΠΌΠ°ΡΡ Π·Π½Π°ΡΠ΅Π½ΠΈΠ΅ true ΠΈΠ»ΠΈ false ΡΠΎΠΎΡΠ²Π΅ΡΡΡΠ²Π΅Π½Π½ΠΎ.
while (current.getKey() != deleteKey) {
parent = current;
if (deleteKey < current.getKey()) {
current = current.getLeftChild();
isLeftChild = true;
} else {
isLeftChild = false;
current = current.getRightChild();
}
if (current == null)
return false;
}
if (current.getLeftChild() == null && current.getRightChild() == null) {//ΠΏΠ΅ΡΠ²ΡΠΉ ΡΠ»ΡΡΠ°ΠΉ
if (current == root)
current = null;
else if (isLeftChild)
parent.setLeftChild(null);
else
parent.setRightChild(null);
}
else if (current.getRightChild() == null) {//Π²ΡΠΎΡΠΎΠΉ ΡΠ»ΡΡΠ°ΠΉ
if (current == root)
root = current.getLeftChild();
else if (isLeftChild)
parent.setLeftChild(current.getLeftChild());
else
current.setRightChild(current.getLeftChild());
} else if (current.getLeftChild() == null) {
if (current == root)
root = current.getRightChild();
else if (isLeftChild)
parent.setLeftChild(current.getRightChild());
else
parent.setRightChild(current.getRightChild());
}
else {//ΡΡΠ΅ΡΠΈΠΉ ΡΠ»ΡΡΠ°ΠΉ
Node<T> successor = getSuccessor(current);
if (current == root)
root = successor;
else if (isLeftChild)
parent.setLeftChild(successor);
else
parent.setRightChild(successor);
}
return true;
}
Konplexutasuna O(log(n))ra hurbildu daiteke.
Zuhaitz batean maximoa/minimoa aurkitzea
Jakina, nola aurkitu zuhaitzean gutxieneko/gehieneko balioa - sekuentzialki zuhaitzaren ezkerreko/eskuineko elementuen katetik joan behar duzu, hurrenez hurren; hostora iristen zarenean, gutxieneko/gehieneko elementua izango da.
public Node<T> getMinimum(Node<T> startPoint) {
Node<T> current = startPoint;
Node<T> parent = current;
while (current != null) {
parent = current;
current = current.getLeftChild();
}
return parent;
}
public Node<T> getMaximum(Node<T> startPoint) {
Node<T> current = startPoint;
Node<T> parent = current;
while (current != null) {
parent = current;
current = current.getRightChild();
}
return parent;
}
Konplexutasuna - O(log(n))
Saihesbide simetrikoa
Traversal zuhaitzaren nodo bakoitza bisitatzea da, horrekin zerbait egiteko.
Gurutze-algoritmo simetriko errekurtsiboa:
- Egin ekintza bat ezkerreko haurraren gainean
- Egin ekintza zure buruarekin
- Egin ekintza bat ume egokiaren gainean
kodea:
public void inOrder(Node<T> current) {
if (current != null) {
inOrder(current.getLeftChild());
System.out.println(current.getData() + " ");//ΠΠ΄Π΅ΡΡ ΠΌΠΎΠΆΠ΅Ρ Π±ΡΡΡ Π²ΡΠ΅, ΡΡΠΎ ΡΠ³ΠΎΠ΄Π½ΠΎ
inOrder(current.getRightChild());
}
}
Ondorioa
Azkenean! Ez badut zerbait azaldu edo iruzkinik badut, iruzkinetan zain nago. Agindu bezala, hona hemen kode osoa.
Node.java:
public class Node<T> {
private T data;
private int key;
private Node<T> leftChild;
private Node<T> rightChild;
public Node(T data, int key) {
this.data = data;
this.key = key;
}
public void setLeftChild(Node<T> newNode) {
leftChild = newNode;
}
public void setRightChild(Node<T> newNode) {
rightChild = newNode;
}
public Node<T> getLeftChild() {
return leftChild;
}
public Node<T> getRightChild() {
return rightChild;
}
public T getData() {
return data;
}
public int getKey() {
return key;
}
}
BinaryTree.java:
public class BinaryTree<T> {
private Node<T> root;
public Node<T> find(int key) {
Node<T> current = root;
while (current.getKey() != key) {
if (key < current.getKey())
current = current.getLeftChild();
else
current = current.getRightChild();
if (current == null)
return null;
}
return current;
}
public void insert(T insertData, int key) {
Node<T> current = root;
Node<T> parent;
Node<T> newNode = new Node<>(insertData, key);
if (root == null)
root = newNode;
else {
while (true) {
parent = current;
if (key < current.getKey()) {
current = current.getLeftChild();
if (current == null) {
parent.setLeftChild(newNode);
return;
}
}
else {
current = current.getRightChild();
if (current == null) {
parent.setRightChild(newNode);
return;
}
}
}
}
}
public Node<T> getMinimum(Node<T> startPoint) {
Node<T> current = startPoint;
Node<T> parent = current;
while (current != null) {
parent = current;
current = current.getLeftChild();
}
return parent;
}
public Node<T> getMaximum(Node<T> startPoint) {
Node<T> current = startPoint;
Node<T> parent = current;
while (current != null) {
parent = current;
current = current.getRightChild();
}
return parent;
}
public Node<T> getSuccessor(Node<T> deleteNode) {
Node<T> parentSuccessor = deleteNode;
Node<T> successor = deleteNode;
Node<T> current = successor.getRightChild();
while (current != null) {
parentSuccessor = successor;
successor = current;
current = current.getLeftChild();
}
if (successor != deleteNode.getRightChild()) {
parentSuccessor.setLeftChild(successor.getRightChild());
successor.setRightChild(deleteNode.getRightChild());
}
return successor;
}
public boolean delete(int deleteKey) {
Node<T> current = root;
Node<T> parent = current;
boolean isLeftChild = false;
while (current.getKey() != deleteKey) {
parent = current;
if (deleteKey < current.getKey()) {
current = current.getLeftChild();
isLeftChild = true;
} else {
isLeftChild = false;
current = current.getRightChild();
}
if (current == null)
return false;
}
if (current.getLeftChild() == null && current.getRightChild() == null) {
if (current == root)
current = null;
else if (isLeftChild)
parent.setLeftChild(null);
else
parent.setRightChild(null);
}
else if (current.getRightChild() == null) {
if (current == root)
root = current.getLeftChild();
else if (isLeftChild)
parent.setLeftChild(current.getLeftChild());
else
current.setRightChild(current.getLeftChild());
} else if (current.getLeftChild() == null) {
if (current == root)
root = current.getRightChild();
else if (isLeftChild)
parent.setLeftChild(current.getRightChild());
else
parent.setRightChild(current.getRightChild());
}
else {
Node<T> successor = getSuccessor(current);
if (current == root)
root = successor;
else if (isLeftChild)
parent.setLeftChild(successor);
else
parent.setRightChild(successor);
}
return true;
}
public void inOrder(Node<T> current) {
if (current != null) {
inOrder(current.getLeftChild());
System.out.println(current.getData() + " ");
inOrder(current.getRightChild());
}
}
}
PS
Endekapena O(n)
Askok ohartuko zineten: zer gertatzen da zuhaitza desorekatu egiten baduzu? Adibidez, jarri nodoak zuhaitzean gero eta gako handiagoak dituztenak: 1,2,3,4,5,6... Ondoren, zuhaitzak zertxobait gogoraraziko du estekatutako zerrenda bat. Eta bai, zuhaitzak bere zuhaitz-egitura galduko du, eta, hortaz, datuen sarbidearen eraginkortasuna. Bilaketa, txertatze eta ezabatze eragiketen konplexutasuna estekatutako zerrenda baten berdina izango da: O(n). Hau da, nire ustez, zuhaitz bitarren desabantaila garrantzitsuenetako bat.
Erregistratutako erabiltzaileek soilik parte hartu dezakete inkestan.
Aspaldi ez naiz HabrΓ©-n egon, eta jakin nahiko nuke zein gairi buruzko zer artikulu gehiago ikustea gustatuko litzaizuke?
-
Datuen Egiturak
-
Algoritmoak (DP, errekurtsioa, datuen konpresioa, etab.)
-
Datu-egiturak eta algoritmoak bizitza errealean aplikatzea
-
Android aplikazioak Javan programatzea
-
Java Web Aplikazioen Programazioa
2 erabiltzailek eman dute botoa. Erabiltzaile 1 abstenitu egin zen.
Iturria: www.habr.com