Prelude
Dësen Artikel ass iwwer binär Sichbeem. Ech hunn viru kuerzem en Artikel iwwer Do hunn ech net vill op binär Beem opgepasst, well d'Sich-, d'Insertiouns- an d'Läschmethoden net relevant waren. Elo hunn ech decidéiert en Artikel iwwer Beem ze schreiwen. Loosst eis ufänken.
E Bam ass eng Datestruktur besteet aus Noden verbonne mat Kanten. Mir kënne soen datt e Bam e spezielle Fall vun enger Grafik ass. Hei ass e Beispill Bam:
Dëst ass kee binäre Sichbaum! Alles ass geschnidden!
Terminologie
Root
Baumwurzel - dëst ass säin héchsten Node. Am Beispill ass dëst Node A. An engem Bam kann nëmmen ee Wee vun der Wuerzel op all aner Node féieren! Tatsächlech kann all Node als Wuerzel vum Subtree ugesi ginn, deen zu dësem Node entsprécht.
Elteren / Nokommen
All Wirbelen ausser d'Wuerzel hu genau ee Rand, deen op en aneren Node féiert. Den Node, deen iwwer dem aktuellen läit, gëtt genannt Elterendeel dësem Node. En Node, deen ënner dem aktuellen läit a mat him verbonnen ass, gëtt genannt Nokommen dësem Node. Loosst eis e Beispill benotzen. Loosst eis Node B huelen, da wäert säin Elterendeel Node A sinn, a seng Kanner wäerten Node D, E a F sinn.
Blat
E Node, dee keng Kanner huet, gëtt e Blat vum Bam genannt. Am Beispill wäerten d'Blieder Node D, E, F, G, I, J, K sinn.
Dëst ass d'Basis Terminologie. Aner Konzepter wäerte weider diskutéiert ginn. Also, e binäre Bam ass e Bam an deem all Node net méi wéi zwee Kanner huet. Wéi Dir Iech virgestallt hutt, wäert de Bam aus dem Beispill net binär sinn, well d'Node B an H méi wéi zwee Kanner hunn. Hei ass e Beispill vun engem binäre Bam:
D'Baumnoden kënnen all Informatioun enthalen. E binäre Sichbaum ass e binäre Bam deen déi folgend Eegeschaften huet:
- Béid lénks a riets Subtrees si binär Sichbeem.
- All Node vum lénksen Subtree vun engem arbiträren Node X hunn Datenschlësselwäerter manner wéi de Wäert vum Dateschlëssel vum Node X selwer.
- All Noden am richtege Subtree vun engem arbiträren Node X hunn Datenschlësselwäerter méi grouss wéi oder gläich wéi de Wäert vum Dateschlëssel vum Node X selwer.
Schlëssel - all Charakteristik vum Node (zum Beispill eng Zuel). De Schlëssel ass néideg fir datt Dir de Bamelement fannt, mat deem dëse Schlëssel entsprécht. Beispill vun engem binäre Sichbaum:
Baum Vue
Wéi mir Fortschrëtter ginn, ginn ech e puer (méiglecherweis onkomplett) Stécker Code fir Äert Verständnis ze verbesseren. De komplette Code wäert um Enn vum Artikel sinn.
E Bam besteet aus Wirbelen. 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;
}
//...остальные методы узла
}
All Node huet zwee Kanner (et ass ganz méiglech datt d'leftChild an / oder rightChild Kanner en Nullwäert enthalen). Dir hutt wahrscheinlech gemierkt datt an dësem Fall d'Zueldaten d'Daten sinn, déi am Node gespäichert sinn; Schlëssel - Node Schlëssel.
Mir hunn de Knuet zortéiert, elo schwätze mer iwwer dréngend Problemer iwwer Beem. Duerno wäert ech mam Wuert "Bam" d'Konzept vun engem binäre Sichbaum mengen. Binär Bam Struktur:
public class BinaryTree<T> {
private Node<T> root;
//методы дерева
}
Mir brauchen nëmmen d'Wuerzel vum Bam als Klass Feld, well vun der Wuerzel, benotzt getLeftChild () an getRightChild () Methoden, kënnt Dir op all Node am Bam kommen.
Algorithmen an engem Bam
Поиск
Loosst eis soen datt Dir e gebaute Bam hutt. Wéi fannt Dir en Element mam Schlësselschlëssel? Dir musst sequenziell vun der Wuerzel erof an de Bam réckelen an de Wäert vum Schlëssel mam Schlëssel vum nächste Knuet vergläichen: wann de Schlëssel manner ass wéi de Schlëssel vum nächste Knuet, da gitt op dat lénkst Kand vum Knuet, wann et ass méi, op déi riets Säit, wann d'Schlësselen gläich sinn, de gewënschte Node fonnt! Relevant 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;
}
Wann de Stroum null gëtt, dann ass d'Sich um Enn vum Bam erreecht (op engem konzeptuellen Niveau sidd Dir op enger net existenter Plaz am Bam - e Kand vun engem Blat).
Loosst eis d'Effizienz vum Sichalgorithmus op engem equilibréierte Bam betruechten (e Bam an deem Knäpper méi oder manner gläichméisseg verdeelt sinn). Da gëtt d'Sicheffizienz O(log(n)), an de Logarithmus ass Basis 2. Kuckt: wann et n Elementer an engem equilibréierte Bam sinn, heescht dat, datt et Log(n) op Basis 2 Niveaue vun der Bam. An op der Sich, an engem Schrëtt vum Zyklus, gitt Dir een Niveau erof.
opginn
Wann Dir d'Essenz vun der Sich begräifen, da wäert d'Insertioun net schwéier fir Iech sinn. Dir musst just op e Blat vum Bam erof goen (no den Ofstamungsregelen, déi an der Sich beschriwwe ginn) a ginn säin Nofolger - lénks oder riets, jee no dem Schlëssel. Ëmsetzung:
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;
}
}
}
}
}
An dësem Fall, nieft dem aktuellen Node, ass et néideg Informatiounen iwwer den Elterendeel vum aktuellen Node ze späicheren. Wann de Stroum gläich Null gëtt, enthält d'Eltervariabel de Blat dee mir brauchen.
D'Effizienz vun der Insertioun wäert selbstverständlech d'selwecht sinn wéi déi vun der Sich - O(log(n)).
Läschen
Entfernung ass déi schwieregst Operatioun déi op engem Bam gemaach muss ginn. Et ass kloer datt mir als éischt d'Element musse fannen dat mir wäerte läschen. Mee wat dann? Wa mir seng Referenz einfach op null setzen, verléiere mir Informatioun iwwer den Ënnerbaum vun deem dësen Node d'Wurzel ass. Methoden fir d'Entfernung vum Bam sinn an dräi Fäll opgedeelt.
Éischte Fall. Den Node deen geläscht gëtt huet keng Kanner
Wann den Node, deen geläscht gëtt, keng Kanner huet, heescht dat datt et e Blat ass. Dofir kënnt Dir einfach d'leftChild oder rightChild Felder vu sengem Elterendeel op null setzen.
Zweete Fall. Den Node fir ze läschen huet ee Kand
Dëse Fall ass och net ganz komplizéiert. Komme mer zréck op eist Beispill. Loosst eis soen, mir mussen en Element mam Schlëssel läschen 14. Averstanen datt well et de richtege Nofolger vun engem Node mat Schlëssel 10 ass, da wäert iergendeen vun hiren Nokommen (an dësem Fall déi richteg) e Schlëssel méi wéi 10 hunn, sou datt Dir kann et einfach aus dem Bam "schneiden", an den Elterendeel direkt mam Kand vum Node verbannen, d.h. konnektéieren den Node mat Schlëssel 10 un Node 13. D'Situatioun wier ähnlech wann et néideg wier en Node ze läschen deen de lénksen Kand vu sengem Elterendeel ass. Denkt drun selwer - eng exakt Analogie.
Drëtte Fall. E Node huet zwee Kanner
De schwieregste Fall. Loosst eis en neit Beispill kucken.
Sich no engem Nofolger
Loosst eis soen, mir mussen en Node mam Schlëssel läschen 25. Wien solle mir op seng Plaz setzen? Ee vu senge Matleefer (Nokommen oder Nokommen vun Nokommen) muss ginn Nofolger(deen deen d'Plaz vun der Node huelen wäert ewechhuelen).
Wéi ze verstoen, wien soll den Nofolger ginn? Intuitiv ass dëst e Knuet am Bam deem säi Schlëssel deen nächste gréisste vum Knuet ass deen geläscht gëtt. Den Algorithmus ass wéi follegt. Dir musst op säi richtege Nofolger goen (ëmmer op de richtege, well et scho gesot gouf datt den Nofolgerschlëssel méi grouss ass wéi de Schlëssel vum Node, deen geläscht gëtt), a gitt dann duerch d'Kette vu lénksen Nokommen vun dësem richtegen Nofolger . Am Beispill wäerte mir op den Node mam Schlëssel 35 goen, an dann erof op d'Blat duerch d'Kette vu senge lénksen Kanner - an dësem Fall besteet dës Kette nëmmen aus dem Node mam Schlëssel 30. Streng gesi kucken mir fir de klengste Node am Set vun Noden méi grouss wéi dee mir no Node sichen.
Nofolger Sich Method Code:
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;
}
Voll Code fir d'Läschmethod:
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;
}
D'Komplexitéit kann op O(log(n)) geschätzt ginn.
Maximum/Minimum an engem Bam ze fannen
Et ass offensichtlech wéi de Minimum / Maximum Wäert an engem Bam ze fannen - Dir musst sequenziell laanscht d'Kette vun lénks / riets Elementer vum Bam plënneren, respektiv; wann Dir op d'Blat kommt, wäert et de Minimum / Maximum Element sinn.
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;
}
Komplexitéit - O(log(n))
Symmetresch Bypass
Traversal besicht all Node vum Bam fir eng Handlung mat him ze maachen.
Rekursive symmetresche Traversal Algorithmus:
- Maachen eng Aktioun op déi lénks Kand
- Maacht eng Aktioun mat Iech selwer
- Maacht eng Aktioun op dat richtegt Kand
Code:
public void inOrder(Node<T> current) {
if (current != null) {
inOrder(current.getLeftChild());
System.out.println(current.getData() + " ");//Здесь может быть все, что угодно
inOrder(current.getRightChild());
}
}
Konklusioun
Endlech! Wann ech näischt erkläert hunn oder Kommentarer hunn, loosst se w.e.g. an de Kommentarer. Wéi versprach, ginn ech de komplette Code.
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
Degeneratioun zu O(n)
Vill vun iech hu vläicht gemierkt: wat wann Dir de Bam onbalancéiert mécht? Zum Beispill, setzen Noden mat erhéijen Schlësselen an engem Bam: 1,2,3,4,5,6 ... Da wäert de Bam e bësse wéi eng verlinkt Lëscht ähnelen. A jo, de Bam wäert seng Bamstruktur verléieren, an dofir d'Effizienz vum Datezougang. D'Komplexitéit vun de Sich-, Insertiouns- a Läschoperatioune gëtt d'selwecht wéi déi vun enger verlinkter Lëscht: O(n). Dëst ass ee vun de wichtegsten, menger Meenung no, Nodeeler vu binäre Beem.
Nëmme registréiert Benotzer kënnen un der Ëmfro deelhuelen. , wann ech glift.
Ech sinn net ganz laang op der Hub, an ech wéilt gären wëssen wat Artikelen iwwer wéi eng Themen Dir wëllt méi gesinn?
-
Daten Strukturen
-
Algorithmen (DP, Rekursioun, Datekompressioun, asw.)
-
Uwendung vun Datestrukturen an Algorithmen am richtege Liewen
-
Programméiere vun Android Uwendungen op Java
-
Programméiere vun Webapplikatiounen op Java
2 Benotzer hunn gestëmmt. 1 Benotzer huet sech enthalen.
Source: www.habr.com