prelud
Ky artikull ka të bëjë me pemët e kërkimit binar. Kohët e fundit kam shkruar një artikull për Atje nuk i kushtova vërtet vëmendje pemëve binare, sepse metodat e kërkimit, futjes, fshirjes nuk ishin relevante. Tani vendosa të shkruaj një artikull për pemët. Ndoshta do të fillojmë.
Një pemë është një strukturë e të dhënave e përbërë nga nyje të lidhura me skaje. Mund të themi se një pemë është një rast i veçantë i një grafi. Këtu është një pemë shembull:
Kjo nuk është një pemë kërkimi binar! Gjithçka është nën prerje!
terminologji
rrënjë
Rrënja e pemës është nyja më e lartë. Në shembull, kjo është nyja A. Në pemë, vetëm një shteg mund të çojë nga rrënja në çdo nyje tjetër! Në fakt, çdo nyje mund të konsiderohet si rrënja e nënpemës që korrespondon me këtë nyje.
Prindërit/pasardhësit
Të gjitha nyjet përveç rrënjës kanë saktësisht një skaj që çon në një nyje tjetër. Nyja mbi nyjen aktuale quhet prind kjo nyje. Quhet një nyje e vendosur nën aktualen dhe e lidhur me të pasardhës kjo nyje. Le të marrim një shembull. Merrni nyjen B, atëherë prindi i saj do të jetë nyja A dhe fëmijët e saj do të jenë nyjet D, E dhe F.
Лист
Një nyje që nuk ka fëmijë quhet gjethe e pemës. Në shembull, nyjet D, E, F, G, I, J, K do të jenë gjethe.
Kjo është terminologjia bazë. Konceptet e tjera do të diskutohen më vonë. Pra, një pemë binare është një pemë në të cilën çdo nyje do të ketë jo më shumë se dy fëmijë. Siç e keni marrë me mend, pema nga shembulli nuk do të jetë binare, sepse nyjet B dhe H kanë më shumë se dy fëmijë. Këtu është një shembull i një peme binare:
Nyjet e pemës mund të përmbajnë çdo informacion. Një pemë binare e kërkimit është një pemë binare që ka vetitë e mëposhtme:
- Të dy nënpemët e majta dhe të djathta janë pemë kërkimi binare.
- Të gjitha nyjet e nënpemës së majtë të një nyje arbitrare X kanë vlera kryesore të të dhënave më pak se vlera e çelësit të të dhënave të vetë nyjës X.
- Të gjitha nyjet e nënpemës së djathtë të një nyje arbitrare X kanë vlera të çelësit të të dhënave më të mëdha se ose të barabarta me vlerën e çelësit të të dhënave të vetë nyjës X.
Ключ - disa karakteristika të nyjës (për shembull, një numër). Çelësi nevojitet për të gjetur elementin e pemës së cilës i përgjigjet ky çelës. Shembull i pemës së kërkimit binar:
pamje peme
Ndërsa vazhdoj, do të përfshij disa pjesë (ndoshta jo të plota) të kodit në mënyrë që të përmirësoj të kuptuarit tuaj. Kodi i plotë do të jetë në fund të artikullit.
Pema përbëhet nga nyje. Struktura e nyjeve:
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;
}
//...остальные методы узла
}
Çdo nyje ka dy fëmijë (është mjaft e mundshme që fëmijët e majtë dhe/ose fëmija i djathtë të jenë nule). Me siguri e keni kuptuar që në këtë rast të dhënat e numrave janë të dhënat e ruajtura në nyje; kyç - kyç nyje.
Ne e kuptuam nyjen, tani le të flasim për problemet e ngutshme për pemët. Në vijim, fjala "pemë" do të nënkuptojë konceptin e një peme kërkimi binar. Struktura binare e pemës:
public class BinaryTree<T> {
private Node<T> root;
//методы дерева
}
Si fushë klase, na duhet vetëm rrënja e pemës, sepse nga rrënja, duke përdorur metodat getLeftChild() dhe getRightChild(), mund të arrini në çdo nyje të pemës.
Algoritmet e pemëve
Kërko
Le të themi se keni një pemë të ndërtuar. Si të gjeni elementin me çelës kyç? Ju duhet të lëvizni në mënyrë sekuenciale nga rrënja poshtë pemës dhe të krahasoni vlerën e çelësit me çelësin e nyjes tjetër: nëse çelësi është më i vogël se çelësi i nyjes tjetër, atëherë shkoni te pasardhësi i majtë i nyjes, nëse më shumë - në të djathtë, nëse çelësat janë të barabartë - gjendet nyja e dëshiruar! Kodi përkatës:
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;
}
Nëse rryma bëhet e pavlefshme, atëherë përsëritja ka arritur në fund të pemës (në një nivel konceptual, ju jeni në një vend joekzistent në pemë - një fëmijë i një gjetheje).
Merrni parasysh efikasitetin e algoritmit të kërkimit në një pemë të balancuar (një pemë në të cilën nyjet shpërndahen pak a shumë në mënyrë të barabartë). Atëherë efikasiteti i kërkimit do të jetë O(log(n)), dhe logaritmi bazë 2. Shih: nëse ka n elementë në një pemë të balancuar, atëherë kjo do të thotë se do të ketë log(n) bazë 2 nivele të pemës. Dhe në kërkim, për një hap të ciklit, ju zbrisni një nivel.
futur
Nëse e keni kuptuar thelbin e kërkimit, atëherë nuk do ta keni të vështirë të kuptoni futjen. Thjesht duhet të zbrisni në gjethen e pemës (sipas rregullave të prejardhjes të përshkruara në kërkim) dhe të bëheni pasardhës i saj - majtas ose djathtas, në varësi të çelësit. Zbatimi:
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;
}
}
}
}
}
Në këtë rast, përveç nyjës aktuale, është e nevojshme të ruhen informacione për prindin e nyjes aktuale. Kur rryma bëhet null, ndryshorja mëmë do të përmbajë fletën që na nevojitet.
Efikasiteti i futjes do të jetë padyshim i njëjtë me atë të kërkimit - O(log(n)).
Largim
Fshirja është operacioni më kompleks që do të duhet të bëhet me një pemë. Është e qartë se së pari do të jetë e nevojshme të gjejmë elementin që do të heqim. Por pastaj çfarë? Nëse thjesht vendosim referencën e saj në null, atëherë do të humbasim informacionin për nënpemën rrënja e së cilës është kjo nyje. Metodat e heqjes së pemëve ndahen në tre raste.
Rasti i parë. Nyja që do të hiqet nuk ka fëmijë.
Nëse nyja që do të fshihet nuk ka fëmijë, do të thotë se është një gjethe. Prandaj, ju thjesht mund t'i caktoni null fushat leftChild ose rightChild të prindit të tij.
Rasti i dytë. Nyja që do të hiqet ka një fëmijë
Edhe ky rast nuk është shumë i vështirë. Le të kthehemi te shembulli ynë. Supozoni se duhet të fshijmë një element me çelësin 14. Pranoni që duke qenë se është fëmija i duhur i një nyje me çelësin 10, atëherë çdo pasardhës i saj (në këtë rast, ai i duhuri) do të ketë një çelës më të madh se 10, kështu që ju mund ta "presë" lehtësisht nga pema dhe ta lidh prindin drejtpërdrejt me fëmijën e nyjës që fshihet, d.m.th. lidhni nyjen me çelësin 10 me nyjen 13. Situata do të ishte e ngjashme nëse do të duhej të fshinim një nyje që është fëmija i majtë i prindit të saj. Mendoni për këtë vetë - një analogji e saktë.
Rasti i tretë. Node ka dy fëmijë
Rasti më i vështirë. Le të hedhim një vështrim në një shembull të ri.
Kërkoni për një pasardhës
Le të themi se duhet të fshijmë nyjen me çelësin 25. Kë të vendosim në vend të saj? Një nga ndjekësit e tij (pasardhës ose pasardhës të pasardhësve) duhet të bëhet pasardhës(ai që do të zërë vendin e nyjës së hequr).
Si e dini se kush duhet të jetë pasardhësi? Intuitivisht, kjo është nyja në pemë, çelësi i së cilës është më i madhi tjetër nga nyja që hiqet. Algoritmi është si më poshtë. Ju duhet të shkoni te fëmija i tij i djathtë (gjithmonë në të djathtën, sepse tashmë u tha se çelësi i pasardhësit është më i madh se çelësi i nyjës që fshihet), dhe më pas kaloni nëpër zinxhirin e fëmijëve të majtë të kësaj të djathte. fëmijë. Në shembull, ne duhet të shkojmë te nyja me çelësin 35, dhe më pas të zbresim zinxhirin e fëmijëve të saj të majtë në fletë - në këtë rast, ky zinxhir përbëhet vetëm nga nyja me çelësin 30. Në mënyrë të rreptë, ne po kërkojmë nyja më e vogël në grupin e nyjeve më e madhe se nyja e dëshiruar.
Kodi i metodës së kërkimit pasardhës:
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;
}
Kodi i plotë i metodës së fshirjes:
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;
}
Kompleksiteti mund të përafrohet me O(log(n)).
Gjetja e maksimumit/minimumit në një pemë
Natyrisht, si të gjeni vlerën minimale / maksimale në pemë - duhet të kaloni në mënyrë sekuenciale përmes zinxhirit të elementeve majtas / djathtas të pemës, përkatësisht; kur të arrini te fleta, do të jetë elementi minimal/maksimal.
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;
}
Kompleksiteti - O(log(n))
Bypass simetrik
Kalimi është një vizitë në secilën nyje të pemës për të bërë diçka me të.
Algoritmi rekurziv i kalimit simetrik:
- Bëni një veprim në fëmijën e majtë
- Bëni një veprim me veten tuaj
- Bëni një veprim për fëmijën e duhur
Kodi:
public void inOrder(Node<T> current) {
if (current != null) {
inOrder(current.getLeftChild());
System.out.println(current.getData() + " ");//Здесь может быть все, что угодно
inOrder(current.getRightChild());
}
}
Përfundim
Më në fund! Nëse nuk kam shpjeguar diçka ose kam ndonjë koment, atëherë jam duke pritur në komente. Siç u premtua, këtu është kodi i plotë.
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
Degjenerimi në O(n)
Shumë prej jush mund ta kenë vënë re: çka nëse e bëni pemën të çekuilibrohet? Për shembull, vendosni nyjet në pemë me çelësa në rritje: 1,2,3,4,5,6... Atëherë pema do të kujtojë disi një listë të lidhur. Dhe po, pema do të humbasë strukturën e saj të pemës, dhe rrjedhimisht efikasitetin e aksesit të të dhënave. Kompleksiteti i operacioneve të kërkimit, futjes dhe fshirjes do të bëhet i njëjtë me atë të një liste të lidhur: O(n). Ky është një nga disavantazhet më të rëndësishme, për mendimin tim, të pemëve binare.
Vetëm përdoruesit e regjistruar mund të marrin pjesë në anketë. , te lutem
Nuk kam qenë në Habré për një kohë të gjatë dhe do të doja të dija se çfarë artikujsh mbi cilat tema do të dëshironit të shihnit më shumë?
-
Strukturat e të dhënave
-
Algoritmet (DP, rekursioni, kompresimi i të dhënave, etj.)
-
Zbatimi i strukturave dhe algoritmeve të të dhënave në jetën reale
-
Programimi i aplikacioneve android në Java
-
Programimi i aplikacioneve në ueb Java
2 përdorues kanë votuar. 1 përdorues abstenoi.
Burimi: www.habr.com