upptakt
Den här artikeln handlar om binära sökträd. Jag skrev nyligen en artikel om Där ägnade jag inte mycket uppmärksamhet åt binära träd, eftersom metoderna för sökning, infogning och radering inte var relevanta. Nu bestämde jag mig för att skriva en artikel om träd. Låt oss börja.
Ett träd är en datastruktur som består av noder sammankopplade med kanter. Vi kan säga att ett träd är ett specialfall av en graf. Här är ett exempel på ett träd:
Detta är inte ett binärt sökträd! Allt är klippt!
terminologi
rot
Trädrot - det här är dess översta nod. I exemplet är detta nod A. I ett träd kan bara en väg leda från roten till vilken annan nod som helst! Faktum är att vilken nod som helst kan betraktas som roten till underträdet som motsvarar denna nod.
Föräldrar/ättlingar
Alla noder utom roten har exakt en kant som leder upp till en annan nod. Noden som ligger ovanför den nuvarande anropas förälder denna nod. En nod som ligger under den nuvarande och ansluten till den kallas ättling denna nod. Låt oss använda ett exempel. Låt oss ta nod B, då kommer dess förälder att vara nod A, och dess barn kommer att vara noder D, E och F.
ark
En nod som inte har några barn kommer att kallas ett blad av trädet. I exemplet kommer bladen att vara noder D, E, F, G, I, J, K.
Detta är den grundläggande terminologin. Andra begrepp kommer att diskuteras vidare. Så, ett binärt träd är ett träd där varje nod inte kommer att ha fler än två barn. Som du gissat kommer trädet från exemplet inte att vara binärt, eftersom noderna B och H har fler än två barn. Här är ett exempel på ett binärt träd:
Trädnoderna kan innehålla vilken information som helst. Ett binärt sökträd är ett binärt träd som har följande egenskaper:
- Både vänster och höger underträd är binära sökträd.
- Alla noder i det vänstra underträdet av en godtycklig nod X har datanyckelvärden mindre än värdet på datanyckeln för själva nod X.
- Alla noder i det högra underträdet av en godtycklig nod X har datanyckelvärden som är större än eller lika med värdet på datanyckeln för själva nod X.
nyckel — någon egenskap hos noden (till exempel ett tal). Nyckeln behövs så att du kan hitta trädelementet som denna nyckel motsvarar. Exempel på ett binärt sökträd:
Trädvy
Allt eftersom vi utvecklas kommer jag att tillhandahålla några (möjligen ofullständiga) kodbitar för att förbättra din förståelse. Hela koden finns i slutet av artikeln.
Ett träd består av noder. Nodstruktur:
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;
}
//...остальные методы узла
}
Varje nod har två barn (det är mycket möjligt att leftChild och/eller rightChild-barnen kommer att innehålla ett nollvärde). Du har förmodligen insett att i det här fallet är nummerdata den data som lagras i noden; nyckel — nodnyckel.
Vi har löst knuten, nu ska vi prata om pressande problem om träd. Med ordet "träd" menar jag härefter begreppet ett binärt sökträd. Binär trädstruktur:
public class BinaryTree<T> {
private Node<T> root;
//методы дерева
}
Vi behöver bara roten av trädet som ett klassfält, för från roten, med metoderna getLeftChild() och getRightChild() kan du komma till vilken nod som helst i trädet.
Algoritmer i ett träd
Sök
Låt oss säga att du har ett konstruerat träd. Hur hittar man ett element med nyckeln? Du måste sekventiellt flytta från roten ner i trädet och jämföra nyckelns värde med nyckeln för nästa nod: om nyckeln är mindre än nyckeln för nästa nod, gå till vänster avkomling av noden, om den är större, till höger, om nycklarna är lika, hittas den önskade noden! Relevant kod:
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;
}
Om strömmen blir noll har sökningen nått slutet av trädet (på en begreppsmässig nivå är du på en obefintlig plats i trädet - en ättling till ett löv).
Låt oss överväga effektiviteten av sökalgoritmen på ett balanserat träd (ett träd där noder är fördelade mer eller mindre jämnt). Då blir sökeffektiviteten O(log(n)), och logaritmen är bas 2. Titta: om det finns n element i ett balanserat träd, betyder det att det kommer att finnas log(n) till bas 2 nivåer av träd. Och i sökandet, i ett steg i cykeln, går du ner en nivå.
infoga
Om du förstår kärnan i sökningen kommer det inte att vara svårt för dig att förstå infogningen. Du behöver bara gå ner till ett löv på trädet (enligt nedstigningsreglerna som beskrivs i sökningen) och bli dess ättling - vänster eller höger, beroende på nyckeln. Genomförande:
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 det här fallet, förutom den aktuella noden, är det nödvändigt att lagra information om föräldern till den aktuella noden. När ström blir lika med null kommer den överordnade variabeln att innehålla det ark vi behöver.
Effektiviteten för infogning kommer uppenbarligen att vara densamma som för sökning - O(log(n)).
Borttagning
Borttagning är den svåraste operationen som kommer att behöva utföras på ett träd. Det är klart att vi först måste hitta elementet som vi ska ta bort. Men vad då? Om vi helt enkelt ställer in dess referens till null, kommer vi att förlora information om underträdet som denna nod är roten till. Metoderna för borttagning av träd är indelade i tre fall.
Första fallet. Noden som tas bort har inga underordnade
Om noden som tas bort inte har några barn betyder det att det är ett löv. Därför kan du helt enkelt ställa in leftChild- eller rightChild-fälten för dess överordnade till null.
Andra fallet. Noden som ska raderas har ett barn
Det här fallet är inte heller särskilt komplicerat. Låt oss återgå till vårt exempel. Låt oss säga att vi måste ta bort ett element med nyckel 14. Håll med om att eftersom det är den högra avkomlingen till en nod med nyckel 10, så kommer vilken som helst av dess avkomlingar (i det här fallet den högra) att ha en nyckel som är större än 10, så du kan enkelt "klippa ut" det ur trädet, och koppla föräldern direkt till barnet till noden som raderas, d.v.s. koppla noden med nyckel 10 till nod 13. Situationen skulle vara liknande om det var nödvändigt att ta bort en nod som är det vänstra barnet till sin förälder. Tänk på det själv - en exakt analogi.
Tredje fallet. En nod har två barn
Det svåraste fallet. Låt oss titta på ett nytt exempel.
Sök efter en efterträdare
Låt oss säga att vi behöver ta bort en nod med nyckel 25. Vem ska vi sätta i dess ställe? En av hans anhängare (ättlingar eller ättlingar till ättlingar) måste bli efterträdare(den som kommer att ta platsen för noden som tas bort).
Hur förstår man vem som ska bli efterträdaren? Intuitivt är detta en nod i trädet vars nyckel är den näst största från noden som tas bort. Algoritmen är som följer. Du måste gå till dess högra ättling (alltid till den högra, eftersom det redan har sagts att efterföljarnyckeln är större än nyckeln till den nod som tas bort), och sedan gå igenom kedjan av vänster ättlingar till denna högra ättling . I exemplet skulle vi gå till noden med nyckel 35 och sedan gå ner till bladet genom kedjan av dess vänstra barn - i det här fallet består denna kedja bara av noden med nyckel 30. Strängt taget tittar vi för den minsta noden i uppsättningen noder större än den vi letar efter noden.
Kod för efterträdare för sökmetod:
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;
}
Fullständig kod för raderingsmetoden:
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;
}
Komplexiteten kan approximeras till O(log(n)).
Hitta max/minimum i ett träd
Det är uppenbart hur man hittar det lägsta/högsta värdet i ett träd - du måste sekventiellt flytta längs kedjan av vänster/höger element i trädet, respektive; när du kommer till arket kommer det att vara 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;
}
Komplexitet - O(log(n))
Symmetrisk bypass
Traversal besöker varje nod i trädet för att göra något med det.
Rekursiv symmetrisk traversalalgoritm:
- Gör en åtgärd på det vänstra barnet
- Gör en handling med dig själv
- Gör en åtgärd på rätt barn
Kod:
public void inOrder(Node<T> current) {
if (current != null) {
inOrder(current.getLeftChild());
System.out.println(current.getData() + " ");//Здесь может быть все, что угодно
inOrder(current.getRightChild());
}
}
Slutsats
Till sist! Om jag inte har förklarat något eller har några kommentarer, vänligen lämna dem i kommentarerna. Som utlovat tillhandahåller jag hela 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
Degeneration till O(n)
Många av er kanske har märkt: vad händer om du gör trädet obalanserat? Lägg till exempel noder med ökande nycklar i ett träd: 1,2,3,4,5,6... Då kommer trädet att likna en länkad lista något. Och ja, trädet kommer att förlora sin trädstruktur, och därmed effektiviteten av dataåtkomst. Komplexiteten i sök-, infognings- och raderingsoperationer blir densamma som för en länkad lista: O(n). Detta är en av de viktigaste, enligt min mening, nackdelarna med binära träd.
Endast registrerade användare kan delta i undersökningen. , Snälla du.
Jag har inte varit på navet på länge, och jag skulle vilja veta vilka artiklar om vilka ämnen du skulle vilja se mer av?
-
Data struktur
-
Algoritmer (DP, rekursion, datakomprimering, etc.)
-
Tillämpning av datastrukturer och algoritmer i verkligheten
-
Programmera Android-applikationer i Java
-
Programmering av webbapplikationer i Java
2 användare röstade. 1 användare avstod från att rösta.
Källa: www.habr.com