Prelude
Dit artikel gaat over binaire zoekbomen. Ik heb er onlangs een artikel over geschreven Daar besteedde ik niet veel aandacht aan binaire bomen, omdat de methoden voor zoeken, invoegen en verwijderen niet relevant waren. Nu besloot ik een artikel over bomen te schrijven. Laten we beginnen.
Een boom is een datastructuur die bestaat uit knooppunten die met elkaar zijn verbonden door randen. We kunnen zeggen dat een boom een speciaal geval van een grafiek is. Hier is een voorbeeldboom:
Dit is geen binaire zoekboom! Alles is gesneden!
terminologie
wortel
Boomwortel - dit is het bovenste knooppunt. In het voorbeeld is dit knooppunt A. In een boom kan slechts één pad van de wortel naar een ander knooppunt leiden! In feite kan elk knooppunt worden beschouwd als de wortel van de subboom die met dit knooppunt correspondeert.
Ouders/afstammelingen
Alle knooppunten behalve de wortel hebben precies één rand die naar een ander knooppunt leidt. Het knooppunt dat zich boven het huidige bevindt, wordt aangeroepen ouder dit knooppunt. Een knooppunt dat zich onder het huidige bevindt en ermee verbonden is, wordt aangeroepen afstammeling dit knooppunt. Laten we een voorbeeld gebruiken. Laten we knooppunt B nemen, dan is het ouderknooppunt A en de onderliggende knooppunten D, E en F.
Лист
Een knooppunt zonder kinderen wordt een blad van de boom genoemd. In het voorbeeld zijn de bladeren knooppunten D, E, F, G, I, J, K.
Dit is de basisterminologie. Andere concepten zullen verder worden besproken. Een binaire boom is dus een boom waarin elk knooppunt niet meer dan twee kinderen heeft. Zoals je al raadde, zal de boom uit het voorbeeld niet binair zijn, omdat knooppunten B en H meer dan twee kinderen hebben. Hier is een voorbeeld van een binaire boom:
De boomknooppunten kunnen alle informatie bevatten. Een binaire zoekboom is een binaire boom die de volgende eigenschappen heeft:
- Zowel de linker als de rechter subboom zijn binaire zoekbomen.
- Alle knooppunten van de linker deelboom van een willekeurig knooppunt X hebben datasleutelwaarden die kleiner zijn dan de waarde van de datasleutel van knooppunt X zelf.
- Alle knooppunten in de rechter deelboom van een willekeurig knooppunt X hebben datasleutelwaarden die groter zijn dan of gelijk zijn aan de waarde van de datasleutel van knooppunt X zelf.
sleutel — elk kenmerk van het knooppunt (bijvoorbeeld een getal). De sleutel is nodig zodat u het boomelement kunt vinden waarmee deze sleutel correspondeert. Voorbeeld van een binaire zoekboom:
Boom zicht
Naarmate we vorderen, zal ik enkele (mogelijk onvolledige) stukjes code verstrekken om uw begrip te verbeteren. De volledige code staat aan het einde van het artikel.
Een boom bestaat uit knooppunten. Knoopstructuur:
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;
}
//...остальные методы узла
}
Elk knooppunt heeft twee kinderen (het is heel goed mogelijk dat de leftChild- en/of rightChild-kinderen een nulwaarde bevatten). U realiseerde zich waarschijnlijk dat in dit geval de getalgegevens de gegevens zijn die in het knooppunt zijn opgeslagen; sleutel — knooppuntsleutel.
We hebben de knoop doorgehakt, laten we het nu hebben over dringende problemen met bomen. Hierna zal ik met het woord “boom” het concept van een binaire zoekboom bedoelen. Binaire boomstructuur:
public class BinaryTree<T> {
private Node<T> root;
//методы дерева
}
We hebben alleen de wortel van de boom nodig als klassenveld, omdat je vanaf de wortel, met behulp van de methoden getLeftChild() en getRightChild() naar elk knooppunt in de boom kunt gaan.
Algoritmen in een boom
zoeken
Laten we zeggen dat je een geconstrueerde boom hebt. Hoe vind ik een element met de sleutelsleutel? U moet opeenvolgend van de wortel naar beneden in de boom gaan en de waarde van de sleutel vergelijken met de sleutel van het volgende knooppunt: als de sleutel kleiner is dan de sleutel van het volgende knooppunt, ga dan naar de linker afstammeling van het knooppunt, als dat zo is groter, naar rechts, als de sleutels gelijk zijn, is het gewenste knooppunt gevonden! Relevante 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 de stroom nul wordt, heeft de zoekopdracht het einde van de boom bereikt (op conceptueel niveau bevindt u zich op een niet-bestaande plek in de boom - een afstammeling van een blad).
Laten we eens kijken naar de effectiviteit van het zoekalgoritme voor een gebalanceerde boom (een boom waarin de knooppunten min of meer gelijkmatig zijn verdeeld). Dan is de zoekefficiëntie O(log(n)), en de logaritme is grondtal 2. Kijk: als er n elementen zijn in een gebalanceerde boom, dan betekent dit dat er log(n) zal zijn met grondtal 2 niveaus van de boom. En tijdens het zoeken ga je in één stap van de cyclus één niveau omlaag.
invoegen
Als je de essentie van de zoekopdracht begrijpt, zal het begrijpen van de invoeging niet moeilijk voor je zijn. Je hoeft alleen maar naar een blad van de boom te gaan (volgens de afstammingsregels beschreven in de zoekopdracht) en de afstammeling ervan te 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 is het naast het huidige knooppunt noodzakelijk om informatie op te slaan over het bovenliggende knooppunt van het huidige knooppunt. Wanneer current gelijk wordt aan null, zal de parent-variabele het werkblad bevatten dat we nodig hebben.
De efficiëntie van het invoegen zal uiteraard hetzelfde zijn als die van het zoeken - O(log(n)).
verwijdering
Verwijderen is de moeilijkste handeling die aan een boom moet worden uitgevoerd. Het is duidelijk dat we eerst het element moeten vinden dat we gaan verwijderen. Maar wat dan? Als we de verwijzing eenvoudigweg op null zetten, verliezen we informatie over de subboom waarvan dit knooppunt de root is. Methoden voor het verwijderen van bomen zijn onderverdeeld in drie gevallen.
Eerste geval. Het knooppunt dat wordt verwijderd, heeft geen kinderen
Als het knooppunt dat wordt verwijderd geen kinderen heeft, betekent dit dat het een blad is. Daarom kunt u eenvoudig de velden leftChild of rightChild van het bovenliggende veld op null instellen.
Tweede geval. Het knooppunt dat moet worden verwijderd, heeft één onderliggend knooppunt
Deze zaak is ook niet erg ingewikkeld. Laten we terugkeren naar ons voorbeeld. Laten we zeggen dat we een element met sleutel 14 moeten verwijderen. Ga ermee akkoord dat, aangezien het de juiste afstammeling is van een knooppunt met sleutel 10, elk van zijn afstammelingen (in dit geval de juiste) een sleutel groter dan 10 zal hebben, dus je kan het gemakkelijk uit de boom “knippen” en de ouder rechtstreeks verbinden met het kind van het knooppunt dat wordt verwijderd, d.w.z. verbind het knooppunt met sleutel 10 met knooppunt 13. De situatie zou vergelijkbaar zijn als het nodig zou zijn om een knooppunt te verwijderen dat het linkerkind is van zijn ouder. Denk er zelf eens over na - een exacte analogie.
Derde geval. Een knooppunt heeft twee kinderen
Het moeilijkste geval. Laten we naar een nieuw voorbeeld kijken.
Opvolger zoeken
Laten we zeggen dat we een knooppunt met sleutel 25 moeten verwijderen. Wie moeten we daarvoor in de plaats zetten? Een van zijn volgers (afstammelingen of afstammelingen van nakomelingen) moet worden opvolger(degene die de plaats zal innemen van het knooppunt dat wordt verwijderd).
Hoe te begrijpen wie de opvolger moet worden? Intuïtief is dit een knooppunt in de boom waarvan de sleutel de volgende grootste is vanaf het knooppunt dat wordt verwijderd. Het algoritme is als volgt. Je moet naar de rechter afstammeling gaan (altijd naar de rechter, omdat er al is gezegd dat de opvolgersleutel groter is dan de sleutel van het knooppunt dat wordt verwijderd), en dan door de keten van linker afstammelingen van deze rechter afstammeling gaan . In het voorbeeld zouden we naar het knooppunt met sleutel 35 gaan en dan via de keten van de linker kinderen naar het blad gaan - in dit geval bestaat deze keten alleen uit het knooppunt met sleutel 30. Strikt genomen kijken we voor het kleinste knooppunt in de reeks knooppunten die groter zijn dan het knooppunt waarnaar we op zoek zijn.
Opvolger zoekmethodecode:
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;
}
Volledige code voor de verwijdermethode:
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;
}
De complexiteit kan worden benaderd tot O(log(n)).
Het maximum/minimum in een boom vinden
Het is duidelijk hoe je de minimum/maximum waarde in een boom kunt vinden - je moet respectievelijk opeenvolgend langs de keten van links/rechts elementen van de boom bewegen; wanneer u bij het blad komt, is dit het minimum/maximum-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;
}
Complexiteit - O(log(n))
Symmetrische bypass
Traversal bezoekt elk knooppunt van de boom om er actie mee te ondernemen.
Recursief symmetrisch traversal-algoritme:
- Voer een actie uit op het linkerkind
- Doe een actie met jezelf
- Voer een actie uit op het juiste kind
Code:
public void inOrder(Node<T> current) {
if (current != null) {
inOrder(current.getLeftChild());
System.out.println(current.getData() + " ");//Здесь может быть все, что угодно
inOrder(current.getRightChild());
}
}
Conclusie
Eindelijk! Als ik niets heb uitgelegd of opmerkingen heb, kunt u deze achterlaten in de opmerkingen. Zoals beloofd geef ik de volledige code.
Knooppunt.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
Degeneratie naar O(n)
Velen van jullie hebben het misschien gemerkt: wat als je de boom uit balans brengt? Plaats bijvoorbeeld knooppunten met oplopende sleutels in een boom: 1,2,3,4,5,6... Dan zal de boom enigszins op een gekoppelde lijst lijken. En ja, de boom verliest zijn boomstructuur en daarmee de efficiëntie van de gegevenstoegang. De complexiteit van zoek-, invoeg- en verwijderbewerkingen wordt dezelfde als die van een gekoppelde lijst: O(n). Dit is naar mijn mening een van de belangrijkste nadelen van binaire bomen.
Alleen geregistreerde gebruikers kunnen deelnemen aan het onderzoek. , Alsjeblieft.
Ik ben nog niet zo lang op de hub en ik zou graag willen weten welke artikelen over welke onderwerpen je graag meer zou willen zien?
-
Data structuren
-
Algoritmen (DP, recursie, datacompressie, enz.)
-
Toepassing van datastructuren en algoritmen in het echte leven
-
Android-applicaties programmeren in Java
-
Programmeren van webapplicaties in Java
2 gebruikers hebben gestemd. 1 gebruiker onthield zich van stemming.
Bron: www.habr.com