voorspel
Hierdie artikel handel oor binêre soekbome. Ek het onlangs 'n artikel geskryf oor Daar het ek nie regtig aandag aan binêre bome gegee nie, want die metodes van soek, invoeg, uitvee was nie relevant nie. Nou het ek besluit om 'n artikel oor bome te skryf. Miskien sal ons begin.
'n Boom is 'n datastruktuur wat bestaan uit nodusse wat deur rande verbind is. Ons kan sê dat 'n boom 'n spesiale geval van 'n grafiek is. Hier is 'n voorbeeld boom:
Dit is nie 'n binêre soekboom nie! Alles is onder die knie!
terminologie
wortel
Boomwortel is die boonste nodus. In die voorbeeld is dit nodus A. In die boom kan slegs een pad van die wortel na enige ander nodus lei! Trouens, enige nodus kan beskou word as die wortel van die subboom wat met hierdie nodus ooreenstem.
Ouers/nageslag
Alle nodusse behalwe die wortel het presies een rand wat na 'n ander nodus lei. Die nodus bo die huidige nodus word genoem ouer hierdie nodus. 'n Nodus wat onder die huidige een geleë is en daaraan gekoppel is, word genoem afstammeling hierdie nodus. Kom ons neem 'n voorbeeld. Neem nodus B, dan sal sy ouer nodus A wees, en sy kinders sal nodes D, E en F wees.
vel
'n Knoop wat geen kinders het nie, word 'n blaar van die boom genoem. In die voorbeeld sal nodusse D, E, F, G, I, J, K blare wees.
Dit is die basiese terminologie. Ander konsepte sal later bespreek word. Dus, 'n binêre boom is 'n boom waarin elke nodus nie meer as twee kinders sal hê nie. Soos jy geraai het, sal die boom van die voorbeeld nie binêr wees nie, want nodusse B en H het meer as twee kinders. Hier is 'n voorbeeld van 'n binêre boom:
Die nodusse van die boom kan enige inligting bevat. 'n Binêre soekboom is 'n binêre boom wat die volgende eienskappe het:
- Beide linker- en regtersubbome is binêre soekbome.
- Alle nodusse van die linker subboom van 'n arbitrêre nodus X het datasleutelwaardes minder as die datasleutelwaarde van nodus X self.
- Alle nodusse van die regtersubboom van 'n arbitrêre nodus X het datasleutelwaardes groter as of gelyk aan die waarde van die datasleutel van nodus X self.
sleutel - een of ander kenmerk van die nodus (byvoorbeeld 'n getal). Die sleutel is nodig om die element van die boom waarmee hierdie sleutel ooreenstem, te kan vind. Binêre soekboom voorbeeld:
boom uitsig
Soos ek aangaan, sal ek 'n paar (miskien onvolledige) stukke kode insluit om jou begrip te verbeter. Die volledige kode sal aan die einde van die artikel wees.
Die boom bestaan uit knope. Nodusstruktuur:
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;
}
//...остальные методы узла
}
Elke nodus het twee kinders (dit is heel moontlik dat die leftChild en/of rightChild kinders nul sal wees). Jy het waarskynlik verstaan dat in hierdie geval die getaldata die data is wat in die nodus gestoor is; sleutel - node sleutel.
Ons het die knoop uitgepluis, kom ons praat nou oor die dringende probleme oor bome. Hierna sal die woord "boom" die konsep van 'n binêre soekboom beteken. Binêre boomstruktuur:
public class BinaryTree<T> {
private Node<T> root;
//методы дерева
}
As 'n klasveld het ons net die wortel van die boom nodig, want vanaf die wortel, met behulp van die getLeftChild() en getRightChild() metodes, kan jy by enige nodus van die boom uitkom.
Boom Algoritmes
soek
Kom ons sê jy het 'n geboude boom. Hoe om element met sleutelsleutel te vind? Jy moet opeenvolgend van die wortel af in die boom beweeg en die waarde van sleutel met die sleutel van die volgende knoop vergelyk: as sleutel kleiner is as die sleutel van die volgende knoop, gaan dan na die linker afstammeling van die knoop, indien meer - na regs, as die sleutels gelyk is - die gewenste nodus word gevind! Relevante 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;
}
As stroom nul word, dan het iterasie die einde van die boom bereik (op 'n konseptuele vlak is jy op 'n nie-bestaande plek in die boom - 'n kind van 'n blaar).
Oorweeg die doeltreffendheid van die soekalgoritme op 'n gebalanseerde boom ('n boom waarin nodusse min of meer eweredig versprei is). Dan sal die soekdoeltreffendheid O(log(n)) wees, en die logaritme van die basis 2. Kyk: as daar n elemente in 'n gebalanseerde boom is, dan beteken dit dat daar log(n) basis 2 vlakke van die boom sal wees. En in die soektog, vir een stap van die siklus, gaan jy een vlak af.
voeg
As jy die kern van die soektog begryp het, sal dit nie vir jou moeilik wees om die invoeging te verstaan nie. Jy hoef net af te gaan na die blaar van die boom (volgens die reëls van afkoms wat in die soektog beskryf word) en sy afstammeling word - links of regs, afhangende van die sleutel. Implementering:
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;
}
}
}
}
}
In hierdie geval, bykomend tot die huidige nodus, is dit nodig om inligting oor die ouer van die huidige nodus te stoor. Wanneer stroom nul word, sal die ouerveranderlike die blad bevat wat ons benodig.
Die invoegdoeltreffendheid sal natuurlik dieselfde wees as dié van die soektog - O(log(n)).
Verwydering
Uitvee is die mees komplekse operasie wat met 'n boom gedoen sal moet word. Dit is duidelik dat dit eers nodig sal wees om die element te vind wat ons gaan verwyder. Maar wat dan? As ons bloot sy verwysing op nul stel, sal ons inligting verloor oor die subboom waarvan die wortel hierdie nodus is. Boomverwyderingsmetodes word in drie gevalle verdeel.
Eerste geval. Die nodus wat verwyder moet word, het geen kinders nie.
As die nodus wat uitgevee moet word, geen kinders het nie, beteken dit dat dit 'n blaar is. Daarom kan jy eenvoudig die leftChild- of rightChild-velde van sy ouer op nul stel.
Tweede geval. Die nodus wat verwyder moet word, het een kind
Hierdie saak is ook nie baie moeilik nie. Kom ons gaan terug na ons voorbeeld. Gestel ons moet 'n element met sleutel 14 uitvee. Stem saam dat aangesien dit die regte kind van die nodus met sleutel 10 is, enige van sy afstammelinge (in hierdie geval, die regte een) 'n sleutel groter as 10 sal hê, so jy kan dit maklik uit die boom “sny”, en die ouer direk verbind met die kind van die nodus wat uitgevee word, m.a.w. verbind die nodus met sleutel 10 aan node 13. Die situasie sal soortgelyk wees as ons 'n nodus wat die linkerkind van sy ouer is, moet uitvee. Dink self daaroor - 'n presiese analogie.
Derde geval. Node het twee kinders
Die moeilikste geval. Kom ons kyk na 'n nuwe voorbeeld.
Soek 'n opvolger
Kom ons sê ons moet die nodus verwyder met die sleutel 25. Wie sal ons in die plek daarvan plaas? Een van sy volgelinge (afstammelinge of afstammelinge van nageslag) moet word opvolger(die een wat die plek van die verwyderde nodus sal inneem).
Hoe weet jy wie die opvolger moet wees? Intuïtief is dit die nodus in die boom waarvan die sleutel die volgende grootste is van die nodus wat verwyder word. Die algoritme is soos volg. Jy moet na die regte kind gaan (altyd na die regter een, want daar is reeds gesê dat die sleutel van die opvolger groter is as die sleutel van die nodus wat uitgevee word), en dan deur die ketting van linkerkinders van hierdie regterkant gaan. kind. In die voorbeeld moet ons na die nodus met sleutel 35 gaan, en dan met die ketting van sy linkerkinders afgaan na die blaar - in hierdie geval bestaan hierdie ketting slegs uit die nodus met sleutel 30. Streng gesproke soek ons na die kleinste nodus in die stel nodusse groter as die verlangde nodus.
Opvolger soek metode kode:
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;
}
Die volledige kode van die verwyderingsmetode:
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;
}
Die kompleksiteit kan benader word na O(log(n)).
Vind die maksimum/minimum in 'n boom
Natuurlik, hoe om die minimum / maksimum waarde in die boom te vind - jy moet opeenvolgend deur die ketting van links / regs elemente van die boom gaan, onderskeidelik; wanneer jy by die blaar kom, sal dit die minimum/maksimum element wees.
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;
}
Kompleksiteit - O(log(n))
Simmetriese omleiding
Traversal is 'n besoek aan elke nodus van die boom om iets daarmee te doen.
Rekursiewe simmetriese deurkruisalgoritme:
- Maak 'n aksie op die linker kind
- Maak 'n aksie met jouself
- Doen 'n aksie op die regte kind
Kode:
public void inOrder(Node<T> current) {
if (current != null) {
inOrder(current.getLeftChild());
System.out.println(current.getData() + " ");//Здесь может быть все, что угодно
inOrder(current.getRightChild());
}
}
Gevolgtrekking
Uiteindelik! As ek nie iets verduidelik het of enige kommentaar het nie, dan wag ek in die kommentaar. Soos belowe, hier is die volledige kode.
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
Degenerasie na O(n)
Baie van julle het dalk opgemerk: wat as jy die boom ongebalanseerd laat raak? Plaas byvoorbeeld nodusse in die boom met toenemende sleutels: 1,2,3,4,5,6... Dan sal die boom ietwat aan 'n gekoppelde lys herinner. En ja, die boom sal sy boomstruktuur verloor, en dus die doeltreffendheid van datatoegang. Die kompleksiteit van soek-, invoeg- en uitveebewerkings sal dieselfde word as dié van 'n gekoppelde lys: O(n). Dit is een van die belangrikste, na my mening, nadele van binêre bome.
Slegs geregistreerde gebruikers kan aan die opname deelneem. , asseblief.
Ek was lanklaas op Habré, en ek wil graag weet watter artikels oor watter onderwerpe sal jy meer wil sien?
-
Datastrukture
-
Algoritmes (DP, rekursie, datakompressie, ens.)
-
Toepassing van datastrukture en algoritmes in die werklike lewe
-
Programmering van Android-toepassings in Java
-
Java-webtoepassingsprogrammering
2 gebruikers het gestem. 1 gebruiker het buite stemming gebly.
Bron: www.habr.com