forspill
Denne artikkelen handler om binære søketrær. Jeg skrev nylig en artikkel om Der la jeg ikke mye oppmerksomhet til binære trær, fordi søke-, innsettings- og slettingsmetodene ikke var relevante. Nå bestemte jeg meg for å skrive en artikkel om trær. La oss komme i gang.
Et tre er en datastruktur som består av noder forbundet med kanter. Vi kan si at et tre er et spesialtilfelle av en graf. Her er et eksempeltre:
Dette er ikke et binært søketre! Alt er kuttet!
terminologi
root
Trerot - dette er dens øverste node. I eksemplet er dette node A. I et tre kan bare én sti føre fra roten til en hvilken som helst annen node! Faktisk kan enhver node betraktes som roten til undertreet som tilsvarer denne noden.
Foreldre/etterkommere
Alle noder unntatt roten har nøyaktig en kant som leder opp til en annen node. Noden som ligger over den nåværende kalles forelder denne noden. En node som ligger under den nåværende og koblet til den kalles etterkommer denne noden. La oss bruke et eksempel. La oss ta node B, så vil dens overordnede være node A, og dens barn vil være nodene D, E og F.
ark
En node som ikke har barn vil bli kalt et blad av treet. I eksemplet vil bladene være noder D, E, F, G, I, J, K.
Dette er den grunnleggende terminologien. Andre begreper vil bli diskutert videre. Så et binært tre er et tre der hver node ikke vil ha mer enn to barn. Som du gjettet, vil treet fra eksemplet ikke være binært, fordi nodene B og H har mer enn to barn. Her er et eksempel på et binært tre:
Trenodene kan inneholde all informasjon. Et binært søketre er et binært tre som har følgende egenskaper:
- Både venstre og høyre undertrær er binære søketrær.
- Alle noder i det venstre undertreet til en vilkårlig node X har datanøkkelverdier mindre enn verdien til datanøkkelen til node X selv.
- Alle noder i det høyre undertreet til en vilkårlig node X har datanøkkelverdier som er større enn eller lik verdien av datanøkkelen til node X selv.
Ключ — alle kjennetegn ved noden (for eksempel et tall). Nøkkelen er nødvendig slik at du kan finne treelementet som denne nøkkelen tilsvarer. Eksempel på et binært søketre:
Tre utsikt
Etter hvert som vi går videre, vil jeg gi noen (muligens ufullstendige) kodebiter for å forbedre forståelsen din. Hele koden vil være på slutten av artikkelen.
Et tre består av noder. Nodestruktur:
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;
}
//...остальные методы узла
}
Hver node har to barn (det er godt mulig at leftChild og/eller rightChild-barna vil inneholde en nullverdi). Du har sannsynligvis innsett at i dette tilfellet er talldataene dataene som er lagret i noden; nøkkel — node nøkkel.
Vi har ordnet opp i knuten, la oss nå snakke om presserende problemer om trær. Heretter vil jeg med ordet "tre" mene konseptet med et binært søketre. Binær trestruktur:
public class BinaryTree<T> {
private Node<T> root;
//методы дерева
}
Vi trenger bare roten til treet som et klassefelt, fordi fra roten, ved å bruke metodene getLeftChild() og getRightChild() kan du komme til hvilken som helst node i treet.
Algoritmer i et tre
søk
La oss si at du har et konstruert tre. Hvordan finne et element med nøkkelnøkkelen? Du må sekvensielt flytte fra roten og ned i treet og sammenligne verdien av nøkkel med nøkkelen til neste node: hvis nøkkelen er mindre enn nøkkelen til neste node, gå til venstre etterkommer av noden, hvis den er større, til høyre, hvis nøklene er like, blir ønsket node funnet! Relevant kode:
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 strømmen blir null, har søket nådd slutten av treet (på et konseptuelt nivå er du på et ikke-eksisterende sted i treet - en etterkommer av et blad).
La oss vurdere effektiviteten til søkealgoritmen på et balansert tre (et tre der noder er fordelt mer eller mindre jevnt). Da vil søkeeffektiviteten være O(log(n)), og logaritmen er base 2. Se: hvis det er n elementer i et balansert tre, betyr dette at det vil være log(n) til base 2 nivåer av tre. Og i søk, i ett trinn i syklusen, går du ned ett nivå.
sette inn
Hvis du forstår essensen av søket, vil det ikke være vanskelig for deg å forstå innsettingen. Du trenger bare å gå ned til et blad av treet (i henhold til nedstigningsreglene beskrevet i søket) og bli dens etterkommer - venstre eller høyre, avhengig av nøkkelen. Gjennomføring:
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;
}
}
}
}
}
I dette tilfellet, i tillegg til den gjeldende noden, er det nødvendig å lagre informasjon om forelderen til den gjeldende noden. Når gjeldende blir lik null, vil den overordnede variabelen inneholde arket vi trenger.
Effektiviteten av innsetting vil åpenbart være den samme som for søk - O(log(n)).
Fjerning
Fjerning er den vanskeligste operasjonen som må utføres på et tre. Det er klart at vi først må finne elementet vi skal slette. Men hva da? Hvis vi bare setter referansen til null, vil vi miste informasjon om undertreet som denne noden er roten til. Metoder for fjerning av trær er delt inn i tre tilfeller.
Første tilfelle. Noden som slettes har ingen underordnede
Hvis noden som slettes ikke har noen barn, betyr dette at det er et blad. Derfor kan du ganske enkelt sette leftChild- eller rightChild-feltene til det overordnede til null.
Andre sak. Noden som skal slettes har ett barn
Denne saken er heller ikke særlig komplisert. La oss gå tilbake til vårt eksempel. La oss si at vi må slette et element med nøkkel 14. Enig i at siden det er den høyre etterkommeren av en node med nøkkel 10, så vil enhver av dens etterkommere (i dette tilfellet den høyre) ha en nøkkel større enn 10, så du kan enkelt "klippe" den ut av treet, og koble forelderen direkte til barnet til noden som slettes, dvs. koble noden med nøkkel 10 til node 13. Situasjonen ville vært lik hvis det var nødvendig å slette en node som er venstre underordnede til sin forelder. Tenk på det selv - en eksakt analogi.
Tredje tilfelle. En node har to barn
Den vanskeligste saken. La oss se på et nytt eksempel.
Søk etter en etterfølger
La oss si at vi må slette en node med nøkkel 25. Hvem skal vi sette i stedet? En av hans tilhengere (etterkommere eller etterkommere av etterkommere) må bli etterfølger(den som skal ta plassen til noden som fjernes).
Hvordan forstå hvem som skal bli etterfølgeren? Intuitivt er dette en node i treet hvis nøkkel er den nest største fra noden som slettes. Algoritmen er som følger. Du må gå til høyre etterkommer (alltid til høyre, fordi det allerede har blitt sagt at etterfølgernøkkelen er større enn nøkkelen til noden som slettes), og deretter gå gjennom kjeden av venstre etterkommere av denne høyre etterkommeren . I eksemplet ville vi gå til noden med nøkkel 35, og deretter gå ned til bladet gjennom kjeden til dets venstre barn - i dette tilfellet består denne kjeden kun av noden med nøkkel 30. Strengt tatt ser vi etter for den minste noden i settet med noder større enn den vi ser etter noden.
Kode for etterfølgersøkemetode:
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;
}
Full kode for slettemetoden:
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;
}
Kompleksiteten kan tilnærmes til O(log(n)).
Finne maksimum/minimum i et tre
Det er åpenbart hvordan du finner minimums-/maksimumsverdien i et tre - du må bevege deg sekvensielt langs kjeden av henholdsvis venstre/høyre elementer i treet; når du kommer til arket vil det være minimum/maksimum element.
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;
}
Kompleksitet - O(log(n))
Symmetrisk bypass
Traversal besøker hver node i treet for å gjøre noe med det.
Rekursiv symmetrisk traversalalgoritme:
- Gjør en handling på venstre barn
- Gjør en handling med deg selv
- Gjør en handling på rett barn
Kode:
public void inOrder(Node<T> current) {
if (current != null) {
inOrder(current.getLeftChild());
System.out.println(current.getData() + " ");//Здесь может быть все, что угодно
inOrder(current.getRightChild());
}
}
Konklusjon
Endelig! Hvis jeg ikke har forklart noe eller har noen kommentarer, vennligst legg igjen dem i kommentarene. Som lovet gir jeg hele koden.
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
Degenerasjon til O(n)
Mange av dere har kanskje lagt merke til: hva om du gjør treet ubalansert? Sett for eksempel noder med økende nøkler i et tre: 1,2,3,4,5,6... Da vil treet ligne litt på en lenket liste. Og ja, treet vil miste sin trestruktur, og dermed effektiviteten til datatilgang. Kompleksiteten til søk, innsetting og sletting vil bli den samme som for en koblet 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å navet på veldig lenge, og jeg vil gjerne vite hvilke artikler om hvilke emner du vil se mer av?
-
Datastrukturer
-
Algoritmer (DP, rekursjon, datakomprimering, etc.)
-
Anvendelse av datastrukturer og algoritmer i det virkelige liv
-
Programmering av Android-applikasjoner i Java
-
Programmering av webapplikasjoner i Java
2 brukere stemte. 1 bruker avsto.
Kilde: www.habr.com