Preludium
Ky është një artikull që i kushtohet pemëve binarë të kërkimit. Kohët e fundit kam bërë një artikull në lidhje me Atje nuk i kushtova shumë vëmendje pemëve binarë, pasi metodat e kërkimit, futjes dhe fshirjes nuk ishin aktuale. Tani vendosa të shkruaj një artikull pikërisht mbi pemët. Ndoshta, le të fillojmë.
Një pemë është një strukturë e dhënash që përbëhet nga nyje të lidhura me borde. Mund të themi se një pemë është një rast i veçantë i një grafiku. Ja një shembull peme:
Kjo nuk është një pemë binarë kërkimi! Të gjitha në kapakun!
Termat
Rrënja
Rrënja e pemës është nyja më e sipërme. Në shembullin, kjo është nyja A. Në pemë, nga rrënja te çdo nyje tjetër mund të ketë vetëm një rrugë! Në të vërtetë, çdo nyje mund të konsiderohet si rrënja e nënpemës përkatëse.
Prindër/Pasardhësit
TĂ« gjitha nyjet, pĂ«rveç rrĂ«njĂ«s, kanĂ« pikĂ«risht njĂ« bord qĂ« çon lart nĂ« njĂ« nyje tjetĂ«r. Nyja qĂ« ndodhet mĂ« lart se aktualja quhet prindi i kĂ«saj nyje. Nyja qĂ« ndodhet mĂ« poshtĂ« se aktualja dhe e lidhur me tĂ« quhet pasardhĂ«si i kĂ«saj nyje. Le tĂ« shohim njĂ« shembull. TĂ« marrim nyjĂ«n B, atĂ«herĂ« prindi i saj do tĂ« jetĂ« nyja A, dhe pasardhĂ«sit â nyjet D, E dhe F.
Faqe
Një nyje pa pasardhës do të quhet gjethe e pemës. Në shembull, gjethet do të jenë nyjet D, E, F, G, I, J, K.
Kjo është terminologjia kryesore. Konceptet e tjera do të shqyrtohen më tej. Pra, një pemë binare është një pemë në të cilën çdo nyje do të ketë jo më shumë se dy pasardhës. Siç e keni kuptuar, pema nga shembulli nuk do të jetë binare, pasi nyjet B dhe H kanë më shumë se dy pasardhës. Ja një shembull i një pemë binare:
Në nyjet e pemës mund të gjendet çfarëdo informacioni. Një pemë binare kërkimi është një pemë binare e cila karakterizohet nga këto figura:
- TĂ« dy nĂ«npemĂ«t â e majta dhe e djathta â janĂ« pemĂ« binarĂ« kĂ«rkimi.
- Të gjitha nyjet e nënpemës së majtë të nyjës X kanë vlera të çelësit të të dhënave më të vogla se vlera e çelësit të të dhënave të nyjës X.
- Të gjitha nyjet e nënpemës së djathtë të nyjës X kanë vlera të çelësit të të dhënave më të mëdha ose të barabarta me vlerën e çelësit të të dhënave të nyjës X.
ĂelĂ«si Ă«shtĂ« njĂ« karakteristikĂ« e caktuar e nyjĂ«s (p.sh., numri). ĂelĂ«si Ă«shtĂ« i nevojshĂ«m pĂ«r tĂ« gjetur elementin e pemĂ«s qĂ« pĂ«rputhet me kĂ«tĂ« çelĂ«s. Ja njĂ« shembull i njĂ« pemĂ« binare kĂ«rkimi:
Përfaqësimi i pemës
Gjatë avancimit do të sjell disa (ndoshta të paplota) copa kodi, për të përmirësuar kuptimin tuaj. Kodi i plotë do të jetë në fund të artikullit.
Pema përbëhet nga nyje. Strukturë e nyjës:
public class Node {
private T data;
private int key;
private Node leftChild;
private Node rightChild;
public Node(T data, int key) {
this.data = data;
this.key = key;
}
public Node getLeftChild() {
return leftChild;
}
public Node getRightChild() {
return rightChild;
}
//...metodat e tjera të nyjës
}
Ădo nyje ka dy pasardhĂ«s (padyshim, pasardhĂ«sit leftChild dhe/ose rightChild mund tĂ« pĂ«rmbajnĂ« vlerĂ«n null). Me siguri keni kuptuar qĂ« nĂ« kĂ«tĂ« rast numri i tĂ« dhĂ«nave Ă«shtĂ« tĂ« dhĂ«nat e ruajtura nĂ« nyjĂ«; çelĂ«si Ă«shtĂ« çelĂ«si i nyjĂ«s.
Tani që e kuptuam nyjën, le të flasim për problematikën aktuale të pemëve. Këtu dhe tutje, kur përmendim "pemë", do të nënkuptojmë konceptin e pemës binare të kërkimit. Struktura e pemës binare:
public class BinaryTree {
private Node root;
//metodat e pemës
}
Si një fushë klase do të na nevojitet vetëm rrënja e pemës, pasi nga rrënja me metodave getLeftChild() dhe getRightChild() mund të kalojmë në çdo nyje të pemës.
Algoritmet në pemë
KĂ«rko
Supozoni se keni njĂ« pemĂ« tĂ« ndĂ«rtuar. Si tĂ« gjeni elementin me çelĂ«sin key? Duhet tĂ« lĂ«vizni sistematikisht nga rrĂ«nja poshtĂ« nĂ«pĂ«r pemĂ« dhe tĂ« krahasoni vlerĂ«n e çelĂ«sit me çelĂ«sin e nyjĂ«s nĂ« radhĂ«: nĂ«se çelĂ«si Ă«shtĂ« mĂ« i vogĂ«l se çelĂ«si i nyjĂ«s aktuale, atĂ«herĂ« kaloni te pasardhĂ«si i majtĂ« tĂ« nyjĂ«s, nĂ«se Ă«shtĂ« mĂ« i madh â te pasardhĂ«si i djathtĂ«, nĂ«se çelĂ«sit janĂ« tĂ« barabartĂ« â nyja e kĂ«rkuar Ă«shtĂ« gjetur! Kodi pĂ«rkatĂ«s:
public Node find(int key) {
Node current = root;
while (current.getKey() != key) {
if (key < current.getKey())
current = current.getLeftChild();
else
current = current.getRightChild();
if (current == null)
return null;
}
return current;
}
NĂ«se current bĂ«het e barabartĂ« me null, atĂ«herĂ« do tĂ« thotĂ« se ai shkon deri nĂ« fund tĂ« pemĂ«s (nĂ« nivelin konceptual, ndodheni nĂ« njĂ« vend tĂ« paekzistueshĂ«m tĂ« pemĂ«s â pasardhĂ«si i gjetheve).
Le të shqyrtojmë efikasitetin e algoritmit të kërkimit në një pemë të balancuar (pemë në të cilën nyjet shpërndahen më shumë ose më pak njëlloj). Aty efikasiteti i kërkimit do të jetë O(log(n)), me logaritinë me bazë 2. Shihni: nëse në një pemë të balancuar ka n elementë, kjo do të thotë se do të ketë log(n) me bazë 2 nivele të pemës. Dhe në kërkim, për një hap të ciklit, lëvizni një nivel poshtë.
Shtimi
Nëse e kuptoni thelbin e kërkimit, do t'ju jetë e lehtë të kuptoni futjen. Thjesht duhet të zbritni në degën e pemës (sipas rregullave të zbritjes të përshkruara në kërkim) dhe të bëheni pasardhës i saj - të majtë ose të djathtë, në varësi të çelësit. Realizimi:
public void insert(T insertData, int key) {
Node current = root;
Node parent;
Node 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;
}
}
}
}
}
Në këtë rast, nevojitet të ruhen informacione për prindin e nodit aktual. Kur current të bëhet null, në variablën parent do të ketë informacionin e nevojshëm për ne.
Efikasiteti i futjes do të jetë njësoj si ai i kërkimit - O(log(n)).
Fshirja
Fshirja Ă«shtĂ« operacioni mĂ« i komplikuar qĂ« duhet tĂ« kryhet me pemĂ«n. ĂshtĂ« e qartĂ« se fillimisht duhet tĂ« gjendet elementi qĂ« do tĂ« fshihet. Por çfarĂ« mĂ« pas? NĂ«se thjesht i japim referencĂ«s vlerĂ«n null, do tĂ« humbasim informacionin mbi nĂ«npemĂ«n, rrĂ«nja e sĂ« cilĂ«s Ă«shtĂ« ky nod. Metodat pĂ«r fshirjen e pemĂ«s ndahen nĂ« tri raste.
Rasti i parë. Nodi i fshirë nuk ka pasardhës.
Nëse nodi i fshirë nuk ka pasardhës, atëherë do të thotë se ai është një degë. Prandaj, thjesht mund t'i japim fushave leftChild ose rightChild të prindit të tij vlerën null.
Rasti i dytë. Nodi i fshirë ka një pasardhës.
Ky rast gjithashtu nuk është shumë i komplikuar. Të kthehemi te shembulli ynë. Supozoni se duhet të fshijmë elementin me çelës 14. Pajtohuni se, pasi ai është pasardhës i djathtë i nodit me çelës 10, çdo pasardhës i tij (në këtë rast i djathtë) do të ketë një çelës më të madh se 10, prandaj mund ta 'prishim' lehtësisht nga pema, duke lidhur drejtpërdrejt prindin me pasardhësin e nodit të fshirë, dmth. lidhim nodin me çelës 10 me nodin 13. Një situatë e ngjashme do të ishte nëse do të duhej të fshihnim nodin, që është pasardhës i majtë i prindit të tij. Mendoni për këtë vetë - një analogji e saktë.
Rasti i tretë. Nodi ka dy pasardhës.
Rasti më i komplikuar. Do ta shqyrtojmë me një shembull të ri.
Kërkimi i pasardhësit.
Supozoni se duhet të fshijmë nodin me çelës 25. Kush do të vendosim në vendin e tij? Disa nga pasardhësit e tij (pasardhësit apo pasardhësit e pasardhësve) duhet të bëhen pasardhës(ai që do të zërë vendin e nodit të fshirë).
Si ta kuptojmë kush duhet të bëhet pasardhës? Krejt intuitivisht, është nodi në pemë, çelësi i të cilit është më i madhi pas nodit të fshirë. Algoritmi është i thjeshtë. Duhet të shkojmë te pasardhësi i tij të djathtë (është gjithmonë e djathtë, sepse siç u tha, çelësi i pasardhësit është më i madh se çelësi i nodit të fshirë), dhe pastaj të kalojmë përmes zinxhirit të pasardhësve të majtë të këtij pasardhësi të djathtë. Në shembullin tonë duhet të kalojmë te nodi me çelës 35, dhe pastaj të zbresim deri te degë nëpër zinxhirin e pasardhësve të majtë - në këtë rast, ky zinxhir përbëhet vetëm nga nodi me çelës 30. Në thelb, ne po kërkojmë nodin më të vogël në grupin e nodëve që janë më të mëdhenj se nodi i kërkuar.
Kodi i metodës për kërkimin e pasardhësit:
public Node getSuccessor(Node deleteNode) {
Node parentSuccessor = deleteNode; // prindi i pasardhësit
Node successor = deleteNode; // pasardhësi
Node current = successor.getRightChild(); // thjesht një nod që kalon
while (current != null) {
parentSuccessor = successor;
successor = current;
current = current.getLeftChild();
}
// në daljen e ciklit kemi pasardhësin dhe prindin e pasardhësit
if (successor != deleteNode.getRightChild()) { // nëse pasardhësi nuk është i njëjtë me pasardhësin e djathtë të nodit të fshirë
parentSuccessor.setLeftChild(successor.getRightChild()); // prindi i tij merr pasardhësin, për të mos humbur atë
successor.setRightChild(deleteNode.getRightChild()); // lidhim pasardhësin me pasardhësin e djathtë të nodit të fshirë
}
return successor;
}
Kodi i plotë i metodës delete:
public boolean delete(int deleteKey) {
Node current = root;
Node parent = current;
boolean isLeftChild = false; // Në varësi të asaj nëse nodi që po fshihet është fëmijë i majtë apo i djathtë i prindit të tij, variabli boolean isLeftChild do të marrë vlerën true ose false përkatësisht.
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) { // rasti i parë
if (current == root)
current = null;
else if (isLeftChild)
parent.setLeftChild(null);
else
parent.setRightChild(null);
}
else if (current.getRightChild() == null) { // rasti i dytë
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 { // rasti i tretë
Node successor = getSuccessor(current);
if (current == root)
root = successor;
else if (isLeftChild)
parent.setLeftChild(successor);
else
parent.setRightChild(successor);
}
return true;
}
Kompleksiteti mund të aproksimohet në O(log(n)).
Gjetja e maksimumit/minumit në pemë
E qartĂ«, si tĂ« gjejmĂ« vlerĂ«n minimale/maksimale nĂ« pemĂ« â duhet tĂ« kalojmĂ« nĂ« mĂ«nyrĂ« tĂ« njĂ«pasnjĂ«shme nĂ« zinxhirin e elementĂ«ve tĂ« majtĂ«/djathtĂ« tĂ« pemĂ«s pĂ«rkatĂ«sisht; kur tĂ« arrijmĂ« te gjethet, ato do tĂ« jenĂ« elementi minimal/maksimal.
public Node getMinimum(Node startPoint) {
Node current = startPoint;
Node parent = current;
while (current != null) {
parent = current;
current = current.getLeftChild();
}
return parent;
}
public Node getMaximum(Node startPoint) {
Node current = startPoint;
Node parent = current;
while (current != null) {
parent = current;
current = current.getRightChild();
}
return parent;
}
Kompleksiteti â O(log(n))
Kalim simetrik
Kalim â vizitimi i çdo nodi tĂ« pemĂ«s me qĂ«llim tĂ« kryerjes sĂ« ndonjĂ« veprimi me tĂ«.
Algoritmi i kalimit simetrik rekurziv:
- Kryeni një veprim me fëmijën e majtë
- Kryeni një veprim me veten
- Kryeni një veprim me fëmijën e djathtë
Kodi:
public void inOrder(Node current) {
if (current != null) {
inOrder(current.getLeftChild());
System.out.println(current.getData() + " "); // Këtu mund të jetë gjithçka, çfarëdo krejse
inOrder(current.getRightChild());
}
}
PĂ«rfundimi
Më në fund! Nëse kam ndonjë gjë që nuk e kam sqaruar mjaftueshëm ose ka ndonjë vërejtje, pres në komentet. Siç premtova, po sjell kodin e plotë.
Node.java:
public class Node {
private T data;
private int key;
private Node leftChild;
private Node rightChild;
public Node(T data, int key) {
this.data = data;
this.key = key;
}
public void setLeftChild(Node newNode) {
leftChild = newNode;
}
public void setRightChild(Node newNode) {
rightChild = newNode;
}
public Node getLeftChild() {
return leftChild;
}
public Node getRightChild() {
return rightChild;
}
public T getData() {
return data;
}
public int getKey() {
return key;
}
}
BinaryTree.java:
public class BinaryTree {
private Node root;
public Node find(int key) {
Node 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 current = root;
Node parent;
Node 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 getMinimum(Node startPoint) {
Node current = startPoint;
Node parent = current;
while (current != null) {
parent = current;
current = current.getLeftChild();
}
return parent;
}
public Node getMaximum(Node startPoint) {
Node current = startPoint;
Node parent = current;
while (current != null) {
parent = current;
current = current.getRightChild();
}
return parent;
}
public Node getSuccessor(Node deleteNode) {
Node parentSuccessor = deleteNode;
Node successor = deleteNode;
Node 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 current = root;
Node 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 successor = getSuccessor(current);
if (current == root)
root = successor;
else if (isLeftChild)
parent.setLeftChild(successor);
else
parent.setRightChild(successor);
}
return true;
}
public void inOrder(Node current) {
if (current != null) {
inOrder(current.getLeftChild());
System.out.println(current.getData() + " ");
inOrder(current.getRightChild());
}
}
}
P.S.
Degjenerimi deri në O(n)
Shumë nga ju mund të kenë vënë re: çfarë do të ndodhte nëse do të krijonim një pemë të paekuilibruar? Për shembull, nëse futim në pemë nodet me çelësa në rritje: 1, 2, 3, 4, 5, 6⊠Atëherë, pema do të ngjajë disi me një listë të lidhur. Por po, pema do të humbasë strukturën e saj me pisha, prandaj edhe efikasitetin e aksesit në të dhëna. Kompleksiteti i operacioneve të kërkimit, futjes dhe fshirjes do të bëhet si ai i një liste të lidhur: O(n). Kjo tregon një nga disavantazhet më të rëndësishme të pemëve binare, sipas mendimit tim.
Vetëm përdoruesit e regjistruar mund të marrin pjesë në anketë. , ju lutemi.
Nuk kam kohë më të gjatë në Habrë, dhe do të doja të dija cilat tema dëshironi të shihni më shumë?
Strukturat e të dhënave
Algoritmet (DP, rekursioni, kompresimi i të dhënave etj.)
Përdorimi i strukturave të të dhënave dhe algoritmeve në jetën reale
Programimi i aplikacioneve android në Java
Programimi i aplikacioneve web në Java
Vendosën 2 përdorues. U përmbajt 1 përdorues.
Burimi: habr.com
