Prelūdija
Šis raksts ir par bināro meklēšanas kokiem. Nesen uzrakstīju rakstu par Tur es īsti nepievērsu uzmanību binārajiem kokiem, jo meklēšanas, ievietošanas, dzēšanas metodes nebija aktuālas. Tagad nolēmu uzrakstīt rakstu par kokiem. Varbūt sāksim.
Koks ir datu struktūra, kas sastāv no mezgliem, kas savienoti ar malām. Var teikt, ka koks ir īpašs grafa gadījums. Šeit ir koka piemērs:
Šis nav binārais meklēšanas koks! Viss ir zem griezuma!
Vārdu krājums
sakne
Koka sakne ir augstākais mezgls. Piemērā tas ir mezgls A. Kokā tikai viens ceļš var novest no saknes uz jebkuru citu mezglu! Faktiski jebkuru mezglu var uzskatīt par šim mezglam atbilstošā apakškoka sakni.
Vecāki/pēcnācēji
Visiem mezgliem, izņemot sakni, ir tieši viena mala, kas ved uz citu mezglu. Tiek izsaukts mezgls virs pašreizējā mezgla vecāks šis mezgls. Tiek izsaukts mezgls, kas atrodas zem pašreizējā un ir savienots ar to pēcnācējs šis mezgls. Ņemsim piemēru. Ņemiet mezglu B, tad tā vecākais būs mezgls A un tā atvases būs mezgli D, E un F.
Loksnes
Mezglu, kuram nav bērnu, sauc par koka lapu. Piemērā mezgli D, E, F, G, I, J, K būs lapas.
Šī ir pamata terminoloģija. Citi jēdzieni tiks apspriesti vēlāk. Tātad binārais koks ir koks, kurā katram mezglam būs ne vairāk kā divi bērni. Kā jūs uzminējāt, piemēra koks nebūs binārs, jo mezgliem B un H ir vairāk nekā divi bērni. Šeit ir binārā koka piemērs:
Koka mezglos var būt jebkāda informācija. Binārais meklēšanas koks ir binārs koks, kam ir šādas īpašības:
- Gan kreisais, gan labais apakškoks ir binārie meklēšanas koki.
- Visiem patvaļīga mezgla X kreisā apakškoka mezgliem datu atslēgas vērtības ir mazākas nekā paša mezgla X datu atslēgas vērtība.
- Visiem patvaļīga mezgla X labā apakškoka mezgliem datu atslēgu vērtības ir lielākas vai vienādas ar paša mezgla X datu atslēgas vērtību.
Taustiņš - daži mezgla raksturlielumi (piemēram, skaitlis). Atslēga ir nepieciešama, lai varētu atrast koka elementu, kuram šī atslēga atbilst. Binārās meklēšanas koka piemērs:
koka skats
Turpinot, es iekļaušu dažas (iespējams, nepilnīgas) koda daļas, lai uzlabotu jūsu izpratni. Pilns kods būs raksta beigās.
Koks sastāv no mezgliem. Mezglu struktūra:
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;
}
//...остальные методы узла
}
Katram mezglam ir divi bērni (pilnīgi iespējams, ka leftChild un/vai rightChild bērni būs nulle). Jūs droši vien sapratāt, ka šajā gadījumā skaitļu dati ir mezglā saglabātie dati; atslēga - mezgla atslēga.
Mēs izdomājām mezglu, tagad parunāsim par aktuālajām problēmām saistībā ar kokiem. Turpmāk vārds "koks" nozīmēs binārā meklēšanas koka jēdzienu. Binārā koka struktūra:
public class BinaryTree<T> {
private Node<T> root;
//методы дерева
}
Kā klases lauks mums ir nepieciešama tikai koka sakne, jo no saknes, izmantojot getLeftChild() un getRightChild() metodes, var nokļūt jebkurā koka mezglā.
Koku algoritmi
Meklēt
Pieņemsim, ka jums ir uzbūvēts koks. Kā atrast elementu ar atslēgas atslēgu? Jums ir nepieciešams secīgi pārvietoties no saknes uz leju pa koku un salīdzināt atslēgas vērtību ar nākamā mezgla atslēgu: ja atslēga ir mazāka par nākamā mezgla atslēgu, tad pārejiet uz mezgla kreiso pēcnācēju, ja vairāk - pa labi, ja atslēgas ir vienādas - vēlamais mezgls ir atrasts! Attiecīgais kods:
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;
}
Ja strāva kļūst par nulli, tad iterācija ir sasniegusi koka beigas (konceptuālā līmenī tu atrodies kokā neesošā vietā - lapas bērns).
Apsveriet meklēšanas algoritma efektivitāti līdzsvarotā kokā (kokā, kurā mezgli ir sadalīti vairāk vai mazāk vienmērīgi). Tad meklēšanas efektivitāte būs O(log(n)), un logaritms 2. bāze Skat.: ja sabalansētā kokā ir n elementi, tad tas nozīmē, ka kokam būs log(n) bāzes 2 līmeņi. Un, meklējot vienu cikla posmu, jūs nokāpjat vienu līmeni uz leju.
ievietot
Ja esi uztvēris meklēšanas būtību, tad tev nebūs grūti saprast ievietojumu. Jums vienkārši jānokāpj līdz koka lapai (saskaņā ar meklēšanā aprakstītajiem nolaišanās noteikumiem) un jākļūst par tās pēcnācēju - pa kreisi vai pa labi, atkarībā no atslēgas. Īstenošana:
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;
}
}
}
}
}
Šajā gadījumā papildus pašreizējam mezglam ir jāsaglabā informācija par pašreizējā mezgla vecāku. Kad strāva kļūst par nulli, vecākais mainīgais saturēs mums nepieciešamo lapu.
Ievietošanas efektivitāte acīmredzami būs tāda pati kā meklēšanas efektivitāte - O(log(n)).
Pārcelšanās
Dzēšana ir vissarežģītākā darbība, kas būs jāveic ar koku. Ir skaidrs, ka vispirms būs jāatrod elements, kuru mēs gatavojamies noņemt. Bet ko tad? Ja mēs vienkārši iestatīsim tā atsauci uz nulli, mēs zaudēsim informāciju par apakškoku, kura sakne ir šis mezgls. Koku noņemšanas metodes iedala trīs gadījumos.
Pirmais gadījums. Noņemamajam mezglam nav bērnu.
Ja dzēšamajam mezglam nav bērnu, tas nozīmē, ka tā ir lapa. Tādēļ jūs varat vienkārši iestatīt tā vecāklauku leftChild vai rightChild uz nulli.
Otrais gadījums. Noņemamajam mezglam ir viens bērns
Arī šis gadījums nav īpaši grūts. Atgriezīsimies pie mūsu piemēra. Pieņemsim, ka mums ir jāizdzēš elements ar atslēgu 14. Piekrītiet, ka, tā kā tas ir mezgla ar atslēgu 10 pareizais atvasinātais, jebkuram tā pēcnācējam (šajā gadījumā pareizajam) būs atslēga, kas ir lielāka par 10, tāpēc jūs var viegli “izgriezt” to no koka un savienot vecāku tieši ar dzēšamā mezgla bērnu, t.i. savienojiet mezglu ar atslēgu 10 ar mezglu 13. Situācija būtu līdzīga, ja mums būtu jāizdzēš mezgls, kas ir tā vecāka kreisais pakārtots. Padomājiet par to paši - precīza līdzība.
Trešais gadījums. Nodei ir divi bērni
Sarežģītākais gadījums. Apskatīsim jaunu piemēru.
Meklēt pēcteci
Pieņemsim, ka jānoņem mezgls ar atslēgu 25. Kuru liksim tā vietā? Vienam no viņa sekotājiem (pēcnācējiem vai pēcnācēju pēcnācējiem) ir jākļūst pēctecis(tas, kurš ieņems noņemtā mezgla vietu).
Kā jūs zināt, kuram vajadzētu būt pēctecim? Intuitīvi šis ir mezgls kokā, kura atslēga ir nākamā lielākā no mezgla, kas tiek noņemts. Algoritms ir šāds. Jums jāiet pie tā labā bērna (vienmēr pie labā, jo jau tika teikts, ka pēcteča atslēga ir lielāka par dzēšamā mezgla atslēgu) un pēc tam jāiet cauri šīs labās puses kreiso bērnu ķēdei. bērns. Piemērā mums ir jāiet uz mezglu ar atslēgu 35 un pēc tam jāiet lejup pa tā kreiso bērnu ķēdi līdz lapai - šajā gadījumā šī ķēde sastāv tikai no mezgla ar atslēgu 30. Stingri sakot, mēs meklējam mazākais mezgls mezglu kopā, kas ir lielāks par vēlamo mezglu.
Pēcteču meklēšanas metodes kods:
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;
}
Pilns dzēšanas metodes kods:
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;
}
Sarežģītību var tuvināt līdz O(log(n)).
Maksimuma/minimuma atrašana kokā
Acīmredzot, kā kokā atrast minimālo / maksimālo vērtību - jums ir nepieciešams secīgi iziet cauri koka kreiso / labo elementu ķēdei; kad tiksi pie lapiņas, tas būs minimālais/maksimālais elements.
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;
}
Sarežģītība — O(log(n))
Simetrisks apvedceļš
Traverāls ir katra koka mezgla apmeklējums, lai ar to kaut ko darītu.
Rekursīvs simetriskas šķērsošanas algoritms:
- Veiciet darbību ar kreiso bērnu
- Veiciet darbību ar sevi
- Veiciet darbību ar pareizo bērnu
Kods:
public void inOrder(Node<T> current) {
if (current != null) {
inOrder(current.getLeftChild());
System.out.println(current.getData() + " ");//Здесь может быть все, что угодно
inOrder(current.getRightChild());
}
}
Secinājums
Beidzot! Ja kaut ko nepaskaidroju vai man ir komentāri, tad gaidu komentāros. Kā solīts, šeit ir pilns kods.
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
Deģenerācija līdz O(n)
Daudzi no jums, iespējams, ir pamanījuši: ko darīt, ja liksiet kokam kļūt nelīdzsvarotam? Piemēram, ievietojiet kokā mezglus ar pieaugošajiem taustiņiem: 1,2,3,4,5,6... Tad koks nedaudz atgādinās saistīto sarakstu. Un jā, koks zaudēs savu koka struktūru un līdz ar to arī datu piekļuves efektivitāti. Meklēšanas, ievietošanas un dzēšanas darbību sarežģītība kļūs tāda pati kā saistītajā sarakstā: O(n). Tas ir viens no svarīgākajiem, manuprāt, bināro koku trūkumiem.
Aptaujā var piedalīties tikai reģistrēti lietotāji. , lūdzu.
Es neesmu bijis Habré diezgan ilgu laiku, un es vēlētos uzzināt, kādus rakstus par kādām tēmām jūs vēlētos redzēt vairāk?
-
Datu struktūras
-
Algoritmi (DP, rekursija, datu saspiešana utt.)
-
Datu struktūru un algoritmu pielietošana reālajā dzīvē
-
Android lietojumprogrammu programmēšana Java valodā
-
Java tīmekļa lietojumprogrammu programmēšana
Nobalsoja 2 lietotāji. 1 lietotājs atturējās.
Avots: www.habr.com