Prelude
Dit artikel is gewijd aan binaire zoekbomen. Onlangs heb ik een artikel geschreven over Daarin keek ik niet echt naar binaire bomen, omdat zoek-, invoeg- en verwijdermethoden niet relevant waren. Nu heb ik besloten een artikel specifiek over bomen te schrijven. Laten we beginnen.
Een boom is een datastructuur die bestaat uit knooppunten die met ribben verbonden zijn. Je kunt zeggen dat een boom een bijzondere vorm van een graaf is. Hier is een voorbeeld van een boom:
Dit is geen binaire zoekboom! Alles onder de kat!
Terminologie
Wortel
De wortel van de boom is de bovenste knoop ervan. In het voorbeeld is dat knoop A. In de boom kan er vanaf de wortel naar elke andere knoop slechts één pad leiden! In feite kan elke knoop worden beschouwd als de wortel van het bijbehorende subboom.
Ouders/nakomes
Alle knopen, behalve de wortel, hebben precies één rib die omhoog leidt naar een andere knoop. De knoop die boven de huidige is, wordt genoemd ouder van deze knoop. De knoop die zich onder de huidige bevindt en ermee is verbonden, wordt genoemd nakomeling van deze knoop. Laten we een voorbeeld nemen. Neem knoop B, dan is zijn ouder knoop A, en zijn nakomelingen zijn de knopen D, E en F.
Blad
Een knoop zonder nakomelingen wordt een blad van de boom genoemd. In het voorbeeld zijn de bladeren de knopen D, E, F, G, I, J, K.
Dit is de basisterminologie. Andere concepten zullen later worden besproken. Dus, een binaire boom is een boom waarin elke knoop niet meer dan twee nakomelingen heeft. Zoals je al had vermoed, zal de boom uit het voorbeeld geen binaire zijn, omdat de knopen B en H meer dan twee nakomelingen hebben. Hier is een voorbeeld van een binaire boom:
In de knopen van de boom kan elke informatie zijn. Een binaire zoekboom is een binaire boom met de volgende eigenschappen:
- Beide subbomen – het linker en het rechter – zijn binaire zoekbomen.
- Alle knopen van de linker subboom van een willekeurige knoop X hebben datumsleutelwaarden die kleiner zijn dan de waarde van de datumsleutel van knoop X zelf.
- Alle knopen van de rechter subboom van een willekeurige knoop X hebben datumsleutelwaarden die groter of gelijk zijn aan de waarde van de datumsleutel van knoop X zelf.
Sleutel is een eigenschap van een knoop (bijvoorbeeld een nummer). De sleutel is nodig om het element van de boom te vinden dat bij deze sleutel hoort. Voorbeeld van een binaire zoekboom:
De presentatie van de boom
Naarmate we vorderen, zal ik enkele (mogelijk onvolledige) stukjes code geven om uw begrip te verbeteren. De volledige code zal aan het einde van het artikel zijn.
Een boom bestaat uit knooppunten. De structuur van een knooppunt:
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;
}
//... andere methoden van de knoop
}
Elke knoop heeft twee kinderen (het is goed mogelijk dat de kinderen leftChild en/of rightChild een null-waarde hebben). U hebt waarschijnlijk begrepen dat data hier de gegevens zijn die in de knoop worden opgeslagen; key is de sleutel van de knoop.
Nu we de knoop hebben besproken, laten we het hebben over de actuele problemen met bomen. Hier en verder zal ik met 'boom' verwijzen naar het concept van een binaire zoekboom. De structuur van een binaire boom:
public class BinaryTree<T> {
private Node<T> root;
// methoden van de boom
}
Als klasseveld hebben we alleen de wortel van de boom nodig, omdat we vanaf de wortel met de methoden getLeftChild() en getRightChild() elk knooppunt in de boom kunnen bereiken.
Algoritmen in de boom
Zoeken
Laten we aannemen dat u een boom heeft gebouwd. Hoe vindt u een element met de sleutel key? U moet van de wortel naar beneden door de boom bewegen en de waarde key vergelijken met de sleutel van het huidige knooppunt: als key kleiner is dan de sleutel van het huidige knooppunt, ga dan naar het linkerkind van de knoop, als het groter is, ga dan naar het rechterkind, als de sleutels gelijk zijn — het gezochte knooppunt is gevonden! De bijbehorende code:
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;
}
Als current gelijk wordt aan null, betekent dit dat de doorlooptijd het einde van de boom heeft bereikt (op conceptueel niveau bevindt u zich op een niet-bestaande plaats in de boom — het kind van een blad).
Laten we de efficiëntie van het zoekalgoritme in een gebalanceerde boom bekijken (een boom waarin de knopen meer of minder gelijkmatig zijn verdeeld). In dat geval zal de efficiëntie van het zoeken O(log(n)) zijn, met een logaritme met basis 2. Kijk: als er n elementen in de gebalanceerde boom zijn, betekent dit dat er log(n) met basis 2 niveaus van de boom zullen zijn. En bij het zoeken daalt u met één stap in de lus naar één niveau.
Invoegen
Als je de essentie van het zoeken begrijpt, zal het je geen moeite kosten om de invoeging te begrijpen. Je moet gewoon naar het blad van de boom (volgens de afdaalregels die in het zoeken zijn beschreven) en een nakomeling ervan worden — links of rechts, afhankelijk van de sleutel. Implementatie:
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 dit geval moet je, naast de huidige knoop, informatie opslaan over de ouder van de huidige knoop. Wanneer current null wordt, bevat de variabele parent de benodigde blad.
De efficiëntie van de invoeging zal vanzelfsprekend hetzelfde zijn als die van het zoeken — O(log(n)).
Verwijderen
Verwijderen is de meest complexe operatie die met de boom moet worden uitgevoerd. Het is duidelijk dat we eerst het element moeten vinden dat we willen verwijderen. Maar wat dan? Als we gewoon de referentie null toewijzen, verliezen we de informatie over het onderboompje waarvan deze knoop de wortel is. Verwijdermethoden worden in drie gevallen verdeeld.
Eerste geval. De te verwijderen knoop heeft geen nakomelingen.
Als de te verwijderen knoop geen nakomelingen heeft, betekent dit dat hij een blad is. Dus, we kunnen gewoon de velden leftChild of rightChild van de ouder null toewijzen.
Tweede geval. De te verwijderen knoop heeft één nakomeling.
Dit geval is ook niet al te moeilijk. Laten we terugkeren naar ons voorbeeld. Stel dat we het element met sleutel 14 moeten verwijderen. Je zult het ermee eens zijn dat, aangezien het een rechter nakomeling is van de knoop met sleutel 10, elk van zijn nakomelingen (in dit geval de rechter) een sleutel zal hebben die groter is dan 10, dus we kunnen het gemakkelijk 'uitknippen' uit de boom, en de ouder rechtstreeks verbinden met de nakomeling van de te verwijderen knoop, d.w.z., de knoop met sleutel 10 verbinden met de knoop 13. De situatie zou vergelijkbaar zijn als we een knoop zouden moeten verwijderen die de linker nakomeling van zijn ouder is. Denk hier zelf maar over na — het is een exacte analogie.
Derde geval. De knoop heeft twee nakomelingen.
Het meest complexe geval. Laten we het met een nieuw voorbeeld uitleggen.
Zoeken van de opvolger
Stel dat we een knoop met sleutel 25 moeten verwijderen. Wie stellen we op zijn plaats? Iemand uit zijn opvolgers (afstammelingen of afstammelingen van afstammelingen) moet de opvolger(degene die de plaats van de verwijderde knoop zal innemen).
Hoe begrijp je wie de opvolger moet worden? Intuïtief is het duidelijk dat dit een knoop in de boom is, waarvan de sleutel de volgende grootste is na de verwijderde knoop. Het algoritme is als volgt. We moeten naar zijn rechterafstammeling gaan (altijd naar rechts, want het is al gezegd dat de sleutel van de opvolger groter is dan de sleutel van de verwijderde knoop), en vervolgens de keten van linkerafstammelingen van deze rechterafstammeling doorlopen. In ons voorbeeld moeten we naar de knoop met sleutel 35 gaan en daarna naar beneden gaan naar het blad in de keten van zijn linkerafstammelingen — in dit geval bestaat deze keten alleen uit de knoop met sleutel 30. Strikt genomen zoeken we de kleinste knoop in de set van knopen die groter zijn dan de gezochte knoop.
Code van de methode om de opvolger te vinden:
public Node<T> getSuccessor(Node<T> deleteNode) {
Node<T> parentSuccessor = deleteNode; // ouder van de opvolger
Node<T> successor = deleteNode; // opvolger
Node<T> current = successor.getRightChild(); // gewoon een "huidige" knoop
while (current != null) {
parentSuccessor = successor;
successor = current;
current = current.getLeftChild();
}
// bij het verlaten van de lus hebben we de opvolger en de ouder van de opvolger
if (successor != deleteNode.getRightChild()) { // als de opvolger niet overeenkomt met de rechterafstammeling van de verwijderde knoop
parentSuccessor.setLeftChild(successor.getRightChild()); // dan neemt de ouder de afstammeling van de opvolger over om deze niet te verliezen
successor.setRightChild(deleteNode.getRightChild()); // verbinden de opvolger met de rechterafstammeling van de verwijderde knoop
}
return successor;
}
Volledige code van de delete-methode:
public boolean delete(int deleteKey) {
Node current = root;
Node parent = current;
boolean isLeftChild = false; // Afhankelijk van of de te verwijderen knoop een linkerkind of rechterkind van zijn ouder is, zal de boolean variabele isLeftChild respectievelijk true of false zijn.
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) { // eerste geval
if (current == root)
current = null;
else if (isLeftChild)
parent.setLeftChild(null);
else
parent.setRightChild(null);
}
else if (current.getRightChild() == null) { // tweede geval
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 { // derde geval
Node successor = getSuccessor(current);
if (current == root)
root = successor;
else if (isLeftChild)
parent.setLeftChild(successor);
else
parent.setRightChild(successor);
}
return true;
}
De complexiteit kan worden benaderd als O(log(n)).
Zoeken naar de maximum/minimum in een boom
Overduidelijk, om de minimale/maximale waarde in de boom te vinden - moet je respectievelijk door de keten van linkerkinderen/rechterkinderen van de boom gaan; wanneer je bij een blad komt, is dit het minimale/maximale element.
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;
}
Complexiteit - O(log(n))
Symmetrische traversie
Traversie - elke knoop in de boom bezoeken met als doel er een bepaalde actie mee uit te voeren.
Algoritme voor recursieve symmetrische traversie:
- Voer een actie uit met het linkerkind
- Voer een actie uit met jezelf
- Voer een actie uit met het rechterkind
Code:
public void inOrder(Node current) {
if (current != null) {
inOrder(current.getLeftChild());
System.out.println(current.getData() + " ");// Hier kan alles zijn
inOrder(current.getRightChild());
}
}
Conclusie
Eindelijk! Als ik iets niet goed heb uitgelegd of als er opmerkingen zijn, hoor ik het graag in de reacties. Zoals beloofd, hierbij de volledige code.
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.
Verlies tot O(n)
Velen van jullie hebben misschien opgemerkt: wat als we het zo maken dat de boom ongebalanceerd wordt? Bijvoorbeeld door knopen met oplopende sleutels in de boom te plaatsen: 1,2,3,4,5,6… Dan zal de boom iets gaan lijken op een gelinkte lijst. En ja, de boom zal zijn boommachtige structuur verliezen, en dus ook de efficiëntie van gegevensaccess. De complexiteit van zoek-, insertie- en verwijderbewerkingen wordt zoals die van een gelinkte lijst: O(n). Dit is een van de belangrijkste nadelen van binaire bomen, naar mijn mening.
Alleen geregistreerde gebruikers kunnen deelnemen aan de enquête. , alstublieft.
Ik ben niet zo lang geleden op Habr gekomen, en ik wil graag weten, over welke onderwerpen zouden jullie meer artikelen willen zien?
Gegevensstructuren
Algoritmen (Dynamisch programmeren, recursie, gegevenscompressie, enz.)
Toepassing van gegevensstructuren en algoritmen in het echte leven
Programmeren van Android-applicaties in Java
Programmeren van webapplicaties in Java
2 gebruikers hebben gestemd. 1 gebruiker heeft zich onthouden.
Bron: habr.com
