Forord
Denne artikkelen handler om binære søketre. Jeg skrev nylig en artikkel om Der fokuserte jeg ikke mye på binære trær, siden metoder for søk, innsetting og sletting ikke var aktuelle. Nå har jeg bestemt meg for å skrive en artikkel spesifikt om trær. La oss begynne.
Et tre er en datstruktur bestående av noder koblet sammen med kanter. Man kan si at et tre er et spesialtilfelle av en graf. Her er et eksempel på et tre:
Dette er ikke et binært søketre! Alt under kat!
Terminologi
Rot
Roten av treet er den øverste noden. I eksemplet er dette node A. I treet kan det kun finnes én vei fra roten til hvilken som helst annen node! Egentlig kan enhver node betraktes som roten til det tilsvarende deltreet.
Foreldre / etterkommere
Alle noder, bortsett fra roten, har nøyaktig én kant som går opp til en annen node. En node som ligger over den nåværende noden, kalles forelderen til denne noden. En node som ligger under den nåværende noden og er koblet til den, kalles etterkommeren til denne noden. La oss ta et eksempel. Ta node B, da vil forelderen være node A, og etterkommerne vil være nodene D, E og F.
Blad
En node som ikke har noen etterkommere, kalles et blad i treet. I eksemplet vil bladene være nodene D, E, F, G, I, J, K.
Dette er hovedterminologien. Andre begreper vil bli diskutert senere. Så et binært tre er et tre der hver node har ikke mer enn to etterkommere. Som dere kanskje har gjettet, vil treet fra eksemplet ikke være binært, fordi nodene B og H har mer enn to etterkommere. Her er et eksempel på et binært tre:
Nodene i treet kan inneholde hvilken som helst informasjon. Et binært søketre er et binært tre som er preget av følgende egenskaper:
- Begge deltreene — venstre og høyre — er binære søketre.
- Alle noder i venstre deltre av en tilfeldig node X har datanøkkelverdier som er mindre enn nøkkelverdien til node X.
- Alle noder i høyre deltre av en tilfeldig node X har datanøkkelverdier som er større enn eller lik nøkkelverdien til node X.
Nøkkel — en egenskap ved noden (for eksempel et tall). Nøkkelen er nødvendig for å finne elementet i treet som tilsvarer denne nøkkelen. Eksempel på et binært søketre:
Presentasjon av treet
Etter hvert som jeg går gjennom, vil jeg gi noen (kanskje ufullstendige) kodebiter for å forbedre forståelsen din. Fullstendig kode vil være på slutten av artikkelen.
Treet består av noder. Strukturen til en node:
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;
}
//...andre metoder for noden
}
Hver node har to etterkommere (det kan godt være at etterkommerne leftChild og/eller rightChild inneholder null). Du har sikkert fått med deg at i dette tilfellet er data — dataene som lagres i noden; key — nøkkelen til noden.
Nå som vi har forstått noden, la oss snakke om aktuelle problemer med trær. Her og videre vil jeg med ordet "tre" mene konseptet av et binært søketre. Strukturen til et binært tre:
public class BinaryTree<T> {
private Node<T> root;
//metoder for treet
}
Som et klassefelt trenger vi bare roten av treet, ettersom vi kan nå hvilken som helst node i treet fra roten ved hjelp av metodene getLeftChild() og getRightChild().
Algoritmer i treet
Søk
La oss si at du har et konstruert tre. Hvordan finner man elementet med nøkkelen key? Du må bevege deg fra roten nedover i treet og sammenligne verdien av key med nøkkelen til den nåværende noden: hvis key er mindre enn nøkkelen til den nåværende noden, gå til venstre etterkommer av noden, hvis det er større — til høyre, hvis nøklene er like — så er den ønskede noden funnet! Den tilsvarende koden:
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;
}
Hvis current blir lik null, betyr det at vi har nådd slutten av treet (på et konseptuelt nivå befinner du deg på et ikke-eksisterende sted i treet — en etterkommer av et blad).
Vi vurderer effektiviteten av søkealgoritmen på et balansert tre (et tre der nodene er mer eller mindre jevnt fordelt). Da vil effektiviteten av søket være O(log(n)), der logaritmen er med base 2. Se: hvis det er n elementer i det balanserte treet, betyr det at treet vil ha log(n) nivåer med base 2. I søket, for hvert steg i løkken, går du ned ett nivå.
Innføring
Dersom du har fanget essensen av søket, vil det være enkelt å forstå innsettingen. Du må bare gå ned til bladet i treet (i henhold til nedstigningsreglene beskrevet i søket) og bli dets etterkommere — venstre eller høyre, avhengig av nøkkelen. Implementering:
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;
}
}
}
}
}
I dette tilfellet må vi, i tillegg til den gjeldende noden, lagre informasjon om forelderen til den gjeldende noden. Når current blir lik null, vil variabelen parent inneholde det bladet vi trenger.
Effektiviteten av innsetting vil åpenbart være den samme som for søket — O(log(n)).
Sletting
Sletting er den vanskeligste operasjonen vi må utføre med treet. Det er klart at vi først må finne elementet som vi ønsker å slette. Men hva så? Hvis vi bare setter referansen til null, vil vi miste informasjon om undertrærne, hvis rot er denne noden. Metoder for sletting av treet deles inn i tre tilfeller.
Første tilfelle. Den slettede noden har ingen etterkommere.
Hvis den slettede noden ikke har noen etterkommere, betyr det at den er et blad. Følgelig kan vi bare sette feltene leftChild eller rightChild til forelderen hans til null.
Andre tilfelle. Den slettede noden har én etterkommer.
Dette tilfellet er heller ikke veldig komplisert. La oss gå tilbake til vårt eksempel. La oss si at vi må slette elementet med nøkkel 14. Så lenge det er en høyre etterkommer av noden med nøkkel 10, vil enhver av dens etterkommere (i dette tilfellet høyre) ha en nøkkel som er større enn 10, så vi kan enkelt "kutte" det ut av treet, og koble forelderen direkte til etterkommeren til den slettede noden, dvs. koble noden med nøkkel 10 direkte til noden 13. En lignende situasjon ville være hvis vi måtte slette en node som er venstre etterkommer av forelderen sin. Tenk på det selv — en nøyaktig analogi.
Tredje tilfelle. Noden har to etterkommere.
Det mest komplekse tilfellet. La oss analysere det med et nytt eksempel.
Søke etter etterfølger
La oss si vi må fjerne noden med nøkkelen 25. Hvem skal vi sette i stedet for den? Noen av etterkommerne (eller etterkommernes etterkommere) må bli arvingen(den som vil ta plassen til den fjernede noden).
Hvordan forstår vi hvem som skal bli arvingen? Det er intuitivt klart at det er noden i treet hvis nøkkel er den neste størrelsen større enn den fjernede noden. Algoritmen går som følger. Vi må gå til høyre etterkommer (alltid til høyre, for det har allerede blitt sagt at arvingen har en større nøkkel enn den fjernede noden), og deretter følge kjeden av venstre etterkommere til denne høyre etterkommeren. I eksemplet må vi gå til noden med nøkkel 35, og deretter følge kjeden nedover til bladet av venstre etterkommere — i dette tilfellet består denne kjeden bare av noden med nøkkel 30. Strengt tatt leter vi etter den minste noden i settet av noder som er større enn den søkte noden.
Kode for metoden for å finne arvingen:
public Node getSuccessor(Node deleteNode) {
Node parentSuccessor = deleteNode; // forelder av arvingen
Node successor = deleteNode; // arvingen
Node current = successor.getRightChild(); // bare "gjennomløpende" node
while (current != null) {
parentSuccessor = successor;
successor = current;
current = current.getLeftChild();
}
// Når vi forlater løkken har vi arvingen og forelderen til arvingen
if (successor != deleteNode.getRightChild()) { // hvis arvingen ikke er den samme som høyre etterkommer av den fjernede noden
parentSuccessor.setLeftChild(successor.getRightChild()); // så tar forelderen den etterkommeren av arvingen, så den ikke går tapt
successor.setRightChild(deleteNode.getRightChild()); // kobler arvingen til høyre etterkommer av den fjernede noden
}
return successor;
}
Den komplette koden for metoden delete:
public boolean delete(int deleteKey) {
Node current = root;
Node parent = current;
boolean isLeftChild = false; // Avhengig av om den slettede noden er et venstre eller høyre barn av forelderen, vil boolsk variabel isLeftChild være true eller 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) { // første tilfelle
if (current == root)
current = null;
else if (isLeftChild)
parent.setLeftChild(null);
else
parent.setRightChild(null);
}
else if (current.getRightChild() == null) { // andre tilfelle
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 { // tredje tilfelle
Node successor = getSuccessor(current);
if (current == root)
root = successor;
else if (isLeftChild)
parent.setLeftChild(successor);
else
parent.setRightChild(successor);
}
return true;
}
Kompleksiteten kan tilnærmes til O(log(n)).
Finne maksimum/minimum i treet
Det er åpenbart hvordan man finner minimum/maksimum verdien i treet - man må følge kjeden av venstre/høyre elementer i treet henholdsvis; når man kommer til et blad, vil det være minimum/maksimum elementet.
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;
}
Kompleksitet - O(log(n))
Symmetrisk traversering
Traversering - besøke hver node i treet for å gjøre noe med den.
Algoritmen for rekursiv symmetrisk traversering:
- Gjøre noe med venstre barn
- Gjøre noe med seg selv
- Gjøre noe med høyre barn
Kode:
public void inOrder(Node current) {
if (current != null) {
inOrder(current.getLeftChild());
System.out.println(current.getData() + " "); //Her kan det være alt mulig
inOrder(current.getRightChild());
}
}
Konklusjon
Endelig! Hvis jeg har utelatt noe eller hvis det er noen merknader, ser jeg frem til kommentarene. Som lovet, her er fullstendig kode.
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<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());
}
}
}
P.S.
Degenerering til O(n)
Mange av dere kan ha lagt merke til: hva om vi gjør treet ubalansert? For eksempel, legge inn noder med økende nøkler: 1, 2, 3, 4, 5, 6… Da vil treet minne om en lenket liste. Og ja, treet vil miste sin trefasete struktur, og dermed effektiviteten ved datatilgang. Komplekset av søke-, sette inn og slette operasjoner vil bli som for en lenket liste: O(n). Dette er en av de viktigste, etter min mening, ulempene ved binære trær.
Kun registrerte brukere kan delta i undersøkelsen. , vær så snill.
Jeg har ikke vært på Habr lenge, og jeg lurer på hvilke emner dere ønsker å se flere artikler om?
Datastrukturer
Algoritmer (DP, rekursjon, datakomprimering osv.)
Bruk av datastrukturer og algoritmer i det virkelige liv
Programmering av Android-applikasjoner på Java
Programmering av webapplikasjoner på Java
2 brukere har stemt. 1 bruker avholdt seg.
Kilde: habr.com
Russian
Italian
German
Polish
Estonian
Albanian
Bulgarian
Croatian
Czech
Danish
Dutch
English
French
Hungarian
Latvian
Norwegian
Portuguese
Romanian
Slovak
Slovenian
Spanish
Swedish