preludiu
Acest articol este despre arbori binari de căutare. Am scris recent un articol despre Acolo nu am acordat prea multă atenție arborilor binari, deoarece metodele de căutare, inserare și ștergere nu erau relevante. Acum am decis să scriu un articol despre copaci. Să începem.
Un arbore este o structură de date formată din noduri conectate prin muchii. Putem spune că un arbore este un caz special al unui grafic. Iată un exemplu de arbore:
Acesta nu este un arbore de căutare binar! Totul este tăiat!
terminologie
rădăcină
Rădăcina copacului - acesta este nodul său cel mai de sus. În exemplu, acesta este nodul A. Într-un arbore, doar o cale poate duce de la rădăcină la orice alt nod! De fapt, orice nod poate fi considerat ca rădăcină a subarborelui corespunzător acestui nod.
Părinți/descendenți
Toate nodurile, cu excepția rădăcinii, au exact o margine care duce la un alt nod. Se numește nodul situat deasupra celui actual mamă acest nod. Se numește un nod situat sub cel actual și conectat la acesta descendent acest nod. Să folosim un exemplu. Să luăm nodul B, atunci părintele său va fi nodul A, iar copiii săi vor fi nodurile D, E și F.
foaie
Un nod care nu are copii va fi numit o frunză a copacului. În exemplu, frunzele vor fi nodurile D, E, F, G, I, J, K.
Aceasta este terminologia de bază. Alte concepte vor fi discutate în continuare. Deci, un arbore binar este un arbore în care fiecare nod nu va avea mai mult de doi copii. După cum ați ghicit, arborele din exemplu nu va fi binar, deoarece nodurile B și H au mai mult de doi copii. Iată un exemplu de arbore binar:
Nodurile arborelui pot conține orice informație. Un arbore binar de căutare este un arbore binar care are următoarele proprietăți:
- Atât subarborele din stânga cât și din dreapta sunt arbori de căutare binari.
- Toate nodurile subarborelului din stânga al unui nod arbitrar X au valori ale cheii de date mai mici decât valoarea cheii de date a nodului X însuși.
- Toate nodurile din subarborele din dreapta al unui nod arbitrar X au valori ale cheii de date mai mari sau egale cu valoarea cheii de date a nodului X însuși.
Ключ — orice caracteristică a nodului (de exemplu, un număr). Cheia este necesară pentru a putea găsi elementul arborelui căruia îi corespunde această cheie. Exemplu de arbore binar de căutare:
Vedere în copac
Pe măsură ce progresăm, voi furniza câteva bucăți de cod (posibil incomplete) pentru a vă îmbunătăți înțelegerea. Codul complet va fi la sfârșitul articolului.
Un arbore este format din noduri. Structura nodului:
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;
}
//...остальные методы узла
}
Fiecare nod are doi copii (este foarte posibil ca copiii leftChild și/sau rightChild să conțină o valoare nulă). Probabil v-ați dat seama că în acest caz datele numerice sunt datele stocate în nod; cheie — cheie de nod.
Am rezolvat nodul, acum să vorbim despre probleme stringente legate de copaci. În continuare, prin cuvântul „arbore” voi înțelege conceptul de arbore binar de căutare. Structura arborelui binar:
public class BinaryTree<T> {
private Node<T> root;
//методы дерева
}
Avem nevoie doar de rădăcina arborelui ca câmp de clasă, deoarece de la rădăcină, folosind metodele getLeftChild() și getRightChild(), puteți ajunge la orice nod din arbore.
Algoritmi într-un copac
Căutare
Să presupunem că ai un copac construit. Cum să găsiți un element cu cheia cheie? Trebuie să vă mutați secvențial de la rădăcină în jos în arbore și să comparați valoarea cheii cu cheia următorului nod: dacă cheia este mai mică decât cheia următorului nod, atunci mergeți la descendentul din stânga al nodului, dacă este mai mare, la dreapta, daca cheile sunt egale, se gaseste nodul dorit! Cod relevant:
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;
}
Dacă curentul devine nul, atunci căutarea a ajuns la capătul arborelui (la nivel conceptual, vă aflați într-un loc inexistent din arbore - un descendent al unei frunze).
Să luăm în considerare eficiența algoritmului de căutare pe un arbore echilibrat (un arbore în care nodurile sunt distribuite mai mult sau mai puțin uniform). Atunci eficiența căutării va fi O(log(n)), iar logaritmul este baza 2. Uite: dacă există n elemente într-un arbore echilibrat, atunci aceasta înseamnă că va exista log(n) la nivelurile de bază 2 ale copac. Și în căutare, într-o etapă a ciclului, cobori un nivel.
insera
Dacă înțelegeți esența căutării, atunci înțelegerea inserției nu vă va fi dificilă. Trebuie doar să cobori la o frunză a copacului (conform regulilor de coborâre descrise în căutare) și să devii descendentul acesteia - stânga sau dreapta, în funcție de cheie. Implementare:
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 acest caz, pe lângă nodul curent, este necesară stocarea informațiilor despre părintele nodului curent. Când curentul devine egal cu nul, variabila părinte va conține foaia de care avem nevoie.
Eficiența inserției va fi în mod evident aceeași cu cea a căutării - O(log(n)).
Îndepărtare
Îndepărtarea este cea mai dificilă operațiune care va trebui efectuată pe un copac. Este clar că mai întâi va trebui să găsim elementul pe care urmează să-l ștergem. Dar ce atunci? Dacă pur și simplu îi setăm referința la null, vom pierde informații despre subarborele al cărui nod este rădăcină. Metodele de îndepărtare a copacilor sunt împărțite în trei cazuri.
Primul caz. Nodul care este șters nu are copii
Dacă nodul care este șters nu are copii, atunci aceasta înseamnă că este o frunză. Prin urmare, puteți seta pur și simplu câmpurile leftChild sau rightChild ale părintelui său la nul.
Al doilea caz. Nodul de șters are un copil
Nici acest caz nu este foarte complicat. Să revenim la exemplul nostru. Să presupunem că trebuie să ștergem un element cu cheia 14. Fiți de acord că, deoarece este descendentul drept al unui nod cu cheia 10, atunci oricare dintre descendenții săi (în acest caz cel potrivit) va avea o cheie mai mare decât 10, așa că îl poate „decupa” cu ușurință din arbore și poate conecta părintele direct la copilul nodului care este șters, adică conectați nodul cu cheia 10 la nodul 13. Situația ar fi similară dacă ar fi necesară ștergerea unui nod care este fiul stâng al părintelui său. Gândiți-vă la asta - o analogie exactă.
Al treilea caz. Un nod are doi copii
Cel mai dificil caz. Să ne uităm la un nou exemplu.
Caută un succesor
Să presupunem că trebuie să ștergem un nod cu cheia 25. Pe cine ar trebui să punem în locul lui? Unul dintre urmașii săi (descendenți sau descendenți ai descendenților) trebuie să devină succesor(cel care va lua locul nodului care este eliminat).
Cum să înțelegeți cine ar trebui să devină succesorul? În mod intuitiv, acesta este un nod din arbore a cărui cheie este următoarea cea mai mare de la nodul care este șters. Algoritmul este după cum urmează. Trebuie să mergeți la descendentul său din dreapta (întotdeauna la cel drept, pentru că deja s-a spus că cheia succesorului este mai mare decât cheia nodului care se șterge), apoi treceți prin lanțul de descendenți din stânga acestui descendent din dreapta. . În exemplu, am merge la nodul cu cheia 35, apoi am coborî la frunză prin lanțul copiilor săi stângi - în acest caz, acest lanț este format doar din nodul cu cheia 30. Strict vorbind, căutăm pentru cel mai mic nod din setul de noduri mai mari decât cel pe care îl căutăm nodul.
Codul metodei de căutare succesoare:
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;
}
Cod complet pentru metoda de ștergere:
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;
}
Complexitatea poate fi aproximată la O(log(n)).
Găsirea maximului/minimului într-un copac
Este evident cum să găsiți valoarea minimă/maximă într-un arbore - trebuie să vă deplasați secvențial de-a lungul lanțului de elemente din stânga/dreapta din arbore, respectiv; când ajungi la foaie, acesta va fi elementul minim/maxim.
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;
}
Complexitate - O(log(n))
Bypass simetric
Traversal este vizitarea fiecărui nod al arborelui pentru a face ceva cu el.
Algoritm de traversare simetric recursiv:
- Faceți o acțiune asupra copilului stâng
- Fă o acțiune cu tine însuți
- Faceți o acțiune asupra copilului potrivit
Cod:
public void inOrder(Node<T> current) {
if (current != null) {
inOrder(current.getLeftChild());
System.out.println(current.getData() + " ");//Здесь может быть все, что угодно
inOrder(current.getRightChild());
}
}
Concluzie
In cele din urma! Dacă nu am explicat nimic sau am vreun comentariu, vă rugăm să le lăsați în comentarii. După cum am promis, ofer codul complet.
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
Degenerare la O(n)
Mulți dintre voi poate ați observat: ce se întâmplă dacă faceți copacul dezechilibrat? De exemplu, puneți noduri cu chei crescătoare într-un arbore: 1,2,3,4,5,6... Apoi arborele va semăna oarecum cu o listă legată. Și da, arborele își va pierde structura arborescentă și, prin urmare, eficiența accesului la date. Complexitatea operațiunilor de căutare, inserare și ștergere va deveni aceeași cu cea a unei liste legate: O(n). Acesta este unul dintre cele mai importante, în opinia mea, dezavantaje ale arborilor binari.
Numai utilizatorii înregistrați pot participa la sondaj. , Vă rog.
Nu am fost pe hub de foarte mult timp și aș dori să știu ce articole despre ce subiecte ați dori să vedeți mai mult?
-
Structuri de date
-
Algoritmi (DP, recursivitate, compresie de date etc.)
-
Aplicarea structurilor de date și a algoritmilor în viața reală
-
Programarea aplicațiilor Android în Java
-
Programarea aplicațiilor web în Java
Au votat 2 utilizatori. 1 utilizator s-a abținut.
Sursa: www.habr.com