Prelude
Denne artikel handler om binære søgetræer. Jeg skrev for nylig en artikel om Der var jeg ikke rigtig opmærksom på binære træer, fordi metoderne til at søge, indsætte, slette ikke var relevante. Nu besluttede jeg at skrive en artikel om træer. Måske starter vi.
Et træ er en datastruktur bestående af noder forbundet med kanter. Vi kan sige, at et træ er et specialtilfælde af en graf. Her er et eksempel på et træ:
Dette er ikke et binært søgetræ! Alt er under skæring!
terminologi
rod
Trærod er den øverste knude. I eksemplet er dette node A. I træet kan kun én sti føre fra roden til enhver anden knude! Faktisk kan enhver node betragtes som roden af det undertræ, der svarer til denne node.
Forældre/afkom
Alle noder undtagen roden har nøjagtig en kant, der fører op til en anden node. Noden over den aktuelle node kaldes forælder denne node. En node placeret under den nuværende og forbundet til den kaldes efterkommer denne node. Lad os tage et eksempel. Tag node B, så vil dens forælder være node A, og dens børn vil være noderne D, E og F.
ark
En knude, der ikke har børn, kaldes et blad af træet. I eksemplet vil noderne D, E, F, G, I, J, K være blade.
Dette er den grundlæggende terminologi. Andre begreber vil blive diskuteret senere. Så et binært træ er et træ, hvor hver node ikke vil have mere end to børn. Som du har gættet, vil træet fra eksemplet ikke være binært, fordi noderne B og H har mere end to børn. Her er et eksempel på et binært træ:
Træets noder kan indeholde enhver information. Et binært søgetræ er et binært træ, der har følgende egenskaber:
- Både venstre og højre undertræer er binære søgetræer.
- Alle noder i venstre undertræ af en vilkårlig node X har datanøgleværdier mindre end datanøgleværdien for node X selv.
- Alle noder i det højre undertræ i en vilkårlig node X har datanøgleværdier, der er større end eller lig med værdien af datanøglen for node X selv.
nøgle - nogle karakteristika for noden (f.eks. et tal). Nøglen er nødvendig for at kunne finde det element i træet, som denne nøgle svarer til. Eksempel på binært søgetræ:
træ udsigt
Efterhånden som jeg går videre, vil jeg inkludere nogle (måske ufuldstændige) stykker kode for at forbedre din forståelse. Den fulde kode vil være i slutningen af artiklen.
Træet består af noder. Node struktur:
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 børn (det er meget muligt, at leftChild og/eller rightChild børnene vil være null). Du har sikkert forstået, at i dette tilfælde er nummerdataene de data, der er gemt i noden; nøgle - node nøgle.
Vi fandt ud af knuden, lad os nu tale om de presserende problemer med træer. Herefter vil ordet "træ" betyde begrebet et binært søgetræ. Binær træstruktur:
public class BinaryTree<T> {
private Node<T> root;
//методы дерева
}
Som et klassefelt har vi kun brug for roden af træet, for fra roden, ved hjælp af metoderne getLeftChild() og getRightChild() kan du komme til en hvilken som helst knude i træet.
Træ Algoritmer
søgning
Lad os sige, at du har et bygget træ. Hvordan finder man element med nøglenøgle? Du skal sekventielt flytte fra roden ned i træet og sammenligne værdien af nøgle med nøglen til den næste node: hvis nøglen er mindre end nøglen til den næste node, så gå til venstre efterkommer af noden, hvis mere - til højre, hvis tasterne er ens - den ønskede node er fundet! 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 bliver nul, så har iterationen nået slutningen af træet (på et konceptuelt niveau er du et ikke-eksisterende sted i træet - et barn af et blad).
Overvej effektiviteten af søgealgoritmen på et balanceret træ (et træ, hvor noder er fordelt mere eller mindre jævnt). Så vil søgeeffektiviteten være O(log(n)), og logaritmen base 2. Se: hvis der er n elementer i et balanceret træ, så betyder det, at der vil være log(n) base 2 niveauer i træet. Og i søgningen, efter et trin i cyklussen, går du et niveau ned.
indsætte
Hvis du har fat i essensen af søgningen, så vil det ikke være svært for dig at forstå indsættelsen. Du skal bare gå ned til træets blad (i henhold til reglerne for afstamning beskrevet i søgningen) og blive dets efterkommer - venstre eller højre, afhængigt af nøglen. 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;
}
}
}
}
}
I dette tilfælde er det, ud over den aktuelle node, nødvendigt at gemme information om forælderen til den aktuelle node. Når nuværende bliver nul, vil den overordnede variabel indeholde det ark, vi har brug for.
Indsættelseseffektiviteten vil naturligvis være den samme som søgningen - O(log(n)).
Fjernelse
Sletning er den mest komplekse operation, der skal udføres med et træ. Det er klart, at det først bliver nødvendigt at finde det element, som vi skal fjerne. Men hvad så? Hvis vi blot sætter dens reference til null, så mister vi information om undertræet, hvis rod er denne node. Træfjernelsesmetoder er opdelt i tre tilfælde.
Første tilfælde. Noden, der skal fjernes, har ingen børn.
Hvis noden, der skal slettes, ikke har nogen børn, betyder det, at det er et blad. Derfor kan du blot indstille leftChild- eller rightChild-felterne for dets overordnede til null.
Andet tilfælde. Noden, der skal fjernes, har et barn
Denne sag er heller ikke særlig svær. Lad os gå tilbage til vores eksempel. Antag, at vi skal slette et element med nøgle 14. Enig i, at da det er det rigtige underordnede af noden med nøgle 10, så vil enhver af dens efterkommere (i dette tilfælde den rigtige) have en nøgle større end 10, så du kan nemt "klippe" det fra træet, og forbinde forælderen direkte til barnet af den node, der slettes, dvs. forbinde noden med nøgle 10 til node 13. Situationen ville være den samme, hvis vi skulle slette en node, der er venstre underordnede af dens forælder. Tænk over det selv - en nøjagtig analogi.
Tredje tilfælde. Node har to børn
Den sværeste sag. Lad os tage et kig på et nyt eksempel.
Søg efter en efterfølger
Lad os sige, at vi skal fjerne noden med nøglen 25. Hvem skal vi sætte i stedet for? En af hans tilhængere (efterkommere eller efterkommere af efterkommere) skal blive efterfølger(den, der vil træde i stedet for den fjernede node).
Hvordan ved du, hvem der skal være efterfølgeren? Intuitivt er dette den node i træet, hvis nøgle er den næststørste fra den node, der fjernes. Algoritmen er som følger. Du skal gå til dets højre barn (altid til det højre, fordi det allerede blev sagt, at nøglen til efterfølgeren er større end nøglen til den node, der slettes), og derefter gå gennem kæden af venstre børn af denne højre barn. I eksemplet skal vi navigere til en node med tast 35, og derefter gå ned ad kæden af dens venstre børn til bladet - i dette tilfælde består denne kæde kun af knudepunktet med tast 30. Strengt taget leder vi efter den mindste node i sættet af noder større end den ønskede node.
Efterfølgende søgemetodekode:
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;
}
Den komplette 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)).
At finde maksimum/minimum i et træ
Det er klart, hvordan man finder minimum / maksimum værdien i træet - du skal sekventielt gå gennem kæden af venstre / højre elementer i træet, henholdsvis; når du kommer til bladet, 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 er et besøg i hver knude på træet for at gøre noget ved det.
Rekursiv symmetrisk traversalalgoritme:
- Lav en handling på venstre barn
- Lav en handling med dig selv
- Lav en handling på det rigtige barn
Code:
public void inOrder(Node<T> current) {
if (current != null) {
inOrder(current.getLeftChild());
System.out.println(current.getData() + " ");//Здесь может быть все, что угодно
inOrder(current.getRightChild());
}
}
Konklusion
Endelig! Hvis jeg ikke forklarede noget eller har kommentarer, så venter jeg i kommentarerne. Som lovet, her er den komplette 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
Degeneration til O(n)
Mange af jer har måske bemærket: hvad nu hvis du får træet til at blive ubalanceret? Sæt for eksempel noder i træet med stigende nøgler: 1,2,3,4,5,6... Så vil træet minde lidt om en sammenkædet liste. Og ja, træet vil miste sin træstruktur, og dermed effektiviteten af dataadgang. Kompleksiteten af søge-, indsættelses- og sletningsoperationer bliver den samme som for en sammenkædet liste: O(n). Dette er en af de vigtigste, efter min mening, ulemper ved binære træer.
Kun registrerede brugere kan deltage i undersøgelsen. , Vær venlig.
Jeg har ikke været på Habré ret længe, og jeg vil gerne vide, hvilke artikler om hvilke emner du gerne vil se mere?
-
Datastrukturer
-
Algoritmer (DP, rekursion, datakomprimering osv.)
-
Anvendelse af datastrukturer og algoritmer i det virkelige liv
-
Programmering af Android-applikationer i Java
-
Java webapplikationsprogrammering
2 brugere stemte. 1 bruger undlod at stemme.
Kilde: www.habr.com