Antaŭparolo
Tiu artikolo temas pri binaraj serĉarboj. Mi lastatempe skribis artikolon pri Tie mi ne vere atentis binarajn arbojn, ĉar la metodoj serĉi, enmeti, forigi ne estis trafaj. Nun mi decidis verki artikolon pri arboj. Eble ni komencos.
Arbo estas datumstrukturo konsistanta el nodoj ligitaj per randoj. Ni povas diri, ke arbo estas speciala kazo de grafeo. Jen ekzemplo de arbo:
Ĉi tio ne estas binara serĉarbo! Ĉio estas sub la tranĉo!
Terminologio
Radiko
Arba radiko estas la plej supra nodo. En la ekzemplo, ĉi tio estas nodo A. En la arbo, nur unu vojo povas konduki de la radiko al iu alia nodo! Fakte, ajna nodo povas esti konsiderata kiel la radiko de la subarbo responda al ĉi tiu nodo.
Gepatroj/idoj
Ĉiuj nodoj krom la radiko havas ekzakte unu randon kondukantan al alia nodo. La nodo super la nuna nodo estas vokita gepatro ĉi tiu nodo. Nodo situanta sub la nuna kaj konektita al ĝi estas nomita posteulo ĉi tiu nodo. Ni prenu ekzemplon. Prenu nodon B, tiam ĝia gepatro estos nodo A, kaj ĝiaj infanoj estos nodoj D, E kaj F.
Folio
Nodo kiu ne havas infanojn estas nomita folio de la arbo. En la ekzemplo, nodoj D, E, F, G, I, J, K estos folioj.
Jen la baza terminologio. Aliaj konceptoj estos diskutitaj poste. Do, binara arbo estas arbo en kiu ĉiu nodo havos ne pli ol du filojn. Kiel vi divenis, la arbo de la ekzemplo ne estos binara, ĉar nodoj B kaj H havas pli ol du infanojn. Jen ekzemplo de binara arbo:
La nodoj de la arbo povas enhavi ajnan informon. Duuma serĉarbo estas duuma arbo kiu havas la sekvajn trajtojn:
- Kaj maldekstraj kaj dekstraj subarboj estas binaraj serĉarboj.
- Ĉiuj nodoj de la maldekstra subarbo de arbitra nodo X havas datumŝlosilvalorojn malpli ol la datumŝlosilvaloro de nodo X mem.
- Ĉiuj nodoj de la dekstra subarbo de arbitra nodo X havas datumŝlosilvalorojn pli grandajn ol aŭ egalajn al la valoro de la datumŝlosilo de nodo X mem.
Ключ - iu karakterizo de la nodo (ekzemple nombro). La ŝlosilo estas bezonata por povi trovi la elementon de la arbo al kiu ĉi tiu ŝlosilo respondas. Ekzemplo de binara serĉarbo:
arba vido
Dum mi iras, mi inkludos kelkajn (eble nekompletajn) pecojn de kodo por plibonigi vian komprenon. La plena kodo estos ĉe la fino de la artikolo.
La arbo konsistas el nodoj. Noda strukturo:
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;
}
//...остальные методы узла
}
Ĉiu nodo havas du filojn (estas tute eble, ke la infanoj leftChild kaj/aŭ rightChild estos nulaj). Vi verŝajne komprenis, ke ĉi-kaze la nombro-datumoj estas la datumoj konservitaj en la nodo; ŝlosilo - noda ŝlosilo.
Ni eltrovis la nodon, nun ni parolu pri la urĝaj problemoj pri arboj. Ĉi-poste, la vorto "arbo" signifos la koncepton de binara serĉarbo. Duuma arbostrukturo:
public class BinaryTree<T> {
private Node<T> root;
//методы дерева
}
Kiel klaskampo, ni bezonas nur la radikon de la arbo, ĉar de la radiko, uzante la getLeftChild() kaj getRightChild() metodoj, vi povas atingi ajnan nodon de la arbo.
Arbaj Algoritmoj
Поиск
Ni diru, ke vi havas konstruitan arbon. Kiel trovi elementon kun ŝlosila ŝlosilo? Vi devas sinsekve movi de la radiko malsupren la arbon kaj kompari la valoron de ŝlosilo kun la ŝlosilo de la sekva nodo: se ŝlosilo estas malpli ol la ŝlosilo de la sekva nodo, tiam iru al la maldekstra posteulo de la nodo, se pli - dekstre, se la klavoj estas egalaj - la dezirata nodo troviĝas! Rilata kodo:
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;
}
Se fluo fariĝas nula, tiam ripeto atingis la finon de la arbo (je koncipa nivelo, vi estas en neekzistanta loko en la arbo - infano de folio).
Konsideru la efikecon de la serĉalgoritmo sur ekvilibra arbo (arbo en kiu nodoj estas distribuitaj pli-malpli egale). Tiam la serĉefikeco estos O(log(n)), kaj la baza logaritmo 2. Vidu: se estas n elementoj en ekvilibra arbo, tiam tio signifas ke estos log(n) bazo 2 niveloj de la arbo. Kaj en la serĉo, por unu paŝo de la ciklo, vi malsupreniras unu nivelon.
enigi
Se vi ekkomprenis la esencon de la serĉo, tiam ne estos malfacile por vi kompreni la enmeton. Vi nur bezonas malsupreniri al la folio de la arbo (laŭ la reguloj de deveno priskribitaj en la serĉo) kaj fariĝi ĝia posteulo - maldekstre aŭ dekstre, depende de la ŝlosilo. Efektivigo:
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;
}
}
}
}
}
En ĉi tiu kazo, krom la nuna nodo, necesas konservi informojn pri la gepatro de la nuna nodo. Kiam fluo fariĝas nula, la gepatra variablo enhavos la folion, kiun ni bezonas.
La eniga efikeco evidente estos la sama kiel tiu de la serĉo - O(log(n)).
Forigi
Forigo estas la plej kompleksa operacio, kiu devos esti farita kun arbo. Estas klare, ke unue necesos trovi la elementon, kiun ni forigos. Sed do kio? Se ni simple fiksas ĝian referencon al nulo, tiam ni perdos informojn pri la subarbo kies radiko estas ĉi tiu nodo. Arbaj metodoj estas dividitaj en tri kazojn.
Unua kazo. La forigota nodo ne havas filojn.
Se la forigota nodo ne havas filojn, tio signifas, ke ĝi estas folio. Sekve, vi povas simple agordi la leftChild aŭ rightChild kampoj de ĝia gepatro al nulo.
Dua kazo. La forigota nodo havas unu infanon
Ĉi tiu kazo ankaŭ ne estas tre malfacila. Ni revenu al nia ekzemplo. Supozu, ke ni devas forigi elementon kun ŝlosilo 14. Konsentu, ke ĉar ĝi estas la dekstra filo de la nodo kun ŝlosilo 10, tiam iu ajn el ĝiaj posteuloj (ĉi-kaze, la ĝusta) havos ŝlosilon pli granda ol 10, do vi povas facile "tranĉi" ĝin de la arbo, kaj konekti la gepatron rekte al la infano de la nodo forigita, t.e. konekti la nodon per ŝlosilo 10 al nodo 13. La situacio estus simila se ni devus forigi nodon kiu estas la maldekstra filo de ĝia gepatro. Pensu pri tio mem - preciza analogio.
Tria kazo. Nodo havas du infanojn
La plej malfacila kazo. Ni rigardu novan ekzemplon.
Serĉu posteulon
Ni diru, ke ni devas forigi la nodon per la ŝlosilo 25. Kiun ni metu en ĝian lokon? Unu el liaj sekvantoj (posteuloj aŭ posteuloj de posteuloj) devas fariĝi posteulo(tiu, kiu prenos la lokon de la forigita nodo).
Kiel vi scias, kiu estu la posteulo? Intuicie, ĉi tiu estas la nodo en la arbo kies ŝlosilo estas la venonta plej granda de la nodo forigita. La algoritmo estas kiel sekvas. Vi devas iri al ĝia dekstra infano (ĉiam al la dekstra, ĉar oni jam diris, ke la ŝlosilo de la posteulo estas pli granda ol la ŝlosilo de la forigita nodo), kaj poste trairi la ĉenon de maldekstraj infanoj de ĉi tiu dekstra. infano. En la ekzemplo, ni devas iri al la nodo kun ŝlosilo 35, kaj poste malsupreniri la ĉenon de ĝiaj maldekstraj filoj al la folio - en ĉi tiu kazo, ĉi tiu ĉeno konsistas nur el la nodo kun ŝlosilo 30. Strikte parolante, ni serĉas la plej malgranda nodo en la aro de nodoj pli granda ol la dezirata nodo.
Posta serĉmetoda kodo:
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;
}
La kompleta kodo de la foriga metodo:
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;
}
La komplekseco povas esti proksimuma al O(log(n)).
Trovi la maksimumon/minimumon en arbo
Evidente, kiel trovi la minimuman / maksimuman valoron en la arbo - vi devas sinsekve trairi la ĉenon de maldekstraj / dekstraj elementoj de la arbo, respektive; kiam vi atingos la folio, ĝi estos la minimuma/maksimuma elemento.
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;
}
Komplekseco - O(log(n))
Simetria Pretervojo
Traversal estas vizito al ĉiu nodo de la arbo por fari ion kun ĝi.
Rekursiva simetria krucalgoritmo:
- Faru agon ĉe la maldekstra infano
- Faru agon kun vi mem
- Faru agon sur la ĝusta infano
Kodo:
public void inOrder(Node<T> current) {
if (current != null) {
inOrder(current.getLeftChild());
System.out.println(current.getData() + " ");//Здесь может быть все, что угодно
inOrder(current.getRightChild());
}
}
konkludo
Fine! Se mi ne klarigis ion aŭ havas komentojn, tiam mi atendas en la komentoj. Kiel promesite, jen la kompleta kodo.
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
Degenero al O (n)
Multaj el vi eble rimarkis: kaj se vi malekvilibrigas la arbon? Ekzemple, metu nodojn en la arbon kun kreskantaj klavoj: 1,2,3,4,5,6... Tiam la arbo iom memorigos pri ligita listo. Kaj jes, la arbo perdos sian arban strukturon, kaj tial la efikecon de datuma aliro. La komplekseco de serĉo, enmeto kaj forigo operacioj fariĝos la sama kiel tiu de ligita listo: O(n). Ĉi tio estas unu el la plej gravaj, laŭ mi, malavantaĝoj de binaraj arboj.
Nur registritaj uzantoj povas partopreni la enketon. , bonvolu.
Mi ne estas ĉe Habré dum sufiĉe longa tempo, kaj mi ŝatus scii kiajn artikolojn pri kiuj temoj vi ŝatus vidi pli?
-
Datumaj Strukturoj
-
Algoritmoj (DP, rekurso, datumkunpremado, ktp.)
-
Apliko de datumstrukturoj kaj algoritmoj en reala vivo
-
Programado de android-aplikoj en Java
-
Programado de Java Reta Aplikaĵo
2 uzantoj voĉdonis. 1 uzanto sindetenis.
Fonto: www.habr.com