Pròleg
Aquest article tracta sobre arbres de cerca binaris. Fa poc vaig escriure un article sobre Allà no vaig prestar atenció als arbres binaris, perquè els mètodes de cerca, inserció i supressió no eren rellevants. Ara vaig decidir escriure un article sobre els arbres. Potser començarem.
Un arbre és una estructura de dades formada per nodes connectats per arestes. Podem dir que un arbre és un cas especial de gràfic. Aquí teniu un exemple d'arbre:
Això no és un arbre de cerca binari! Tot està sota el tall!
Terminologia
arran
Arrel de l'arbre és el node superior. A l'exemple, aquest és el node A. A l'arbre, només un camí pot conduir des de l'arrel a qualsevol altre node! De fet, qualsevol node es pot considerar com l'arrel del subarbre corresponent a aquest node.
Pares/fills
Tots els nodes, excepte l'arrel, tenen exactament una vora que condueix a un altre node. S'anomena el node per sobre del node actual pare aquest node. S'anomena un node situat per sota de l'actual i connectat a ell descendent aquest node. Prenguem un exemple. Agafeu el node B, llavors el seu pare serà el node A i els seus fills seran els nodes D, E i F.
Full
Un node que no té fills s'anomena fulla de l'arbre. En l'exemple, els nodes D, E, F, G, I, J, K seran fulles.
Aquesta és la terminologia bàsica. Altres conceptes es parlaran més endavant. Per tant, un arbre binari és un arbre en el qual cada node no tindrà més de dos fills. Com heu endevinat, l'arbre de l'exemple no serà binari, perquè els nodes B i H tenen més de dos fills. Aquí teniu un exemple d'arbre binari:
Els nodes de l'arbre poden contenir qualsevol informació. Un arbre de cerca binari és un arbre binari que té les propietats següents:
- Tant els subarbres esquerre com dret són arbres de cerca binaris.
- Tots els nodes del subarbre esquerre d'un node X arbitrari tenen valors de clau de dades inferiors al valor de clau de dades del mateix node X.
- Tots els nodes del subarbre dret d'un node X arbitrari tenen valors de clau de dades superiors o iguals al valor de la clau de dades del mateix node X.
Clau - alguna característica del node (per exemple, un nombre). La clau és necessària per poder trobar l'element de l'arbre al qual correspon aquesta clau. Exemple d'arbre de cerca binari:
vista d'arbre
A mesura que avança, inclouré alguns fragments de codi (potser incomplets) per tal de millorar la vostra comprensió. El codi complet es trobarà al final de l'article.
L'arbre està format per nodes. Estructura del node:
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;
}
//...остальные методы узла
}
Cada node té dos fills (és molt possible que els fills leftChild i/o rightChild siguin nuls). Segurament heu entès que en aquest cas les dades numèriques són les dades emmagatzemades al node; clau - clau de node.
Hem descobert el nus, ara parlem dels problemes urgents dels arbres. Aquí i a continuació, la paraula "arbre" significarà el concepte d'arbre de cerca binari. Estructura d'arbre binari:
public class BinaryTree<T> {
private Node<T> root;
//методы дерева
}
Com a camp de classe, només necessitem l'arrel de l'arbre, perquè des de l'arrel, utilitzant els mètodes getLeftChild() i getRightChild(), podeu arribar a qualsevol node de l'arbre.
Algoritmes d'arbres
Cercar
Suposem que tens un arbre construït. Com trobar l'element amb la clau? Heu de moure's seqüencialment des de l'arrel cap avall de l'arbre i comparar el valor de la clau amb la clau del següent node: si la clau és menor que la clau del següent node, aneu al descendent esquerre del node, si és més: a la dreta, si les claus són iguals, es troba el node desitjat! Codi rellevant:
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;
}
Si el corrent es torna nul, aleshores la iteració ha arribat al final de l'arbre (a nivell conceptual, esteu en un lloc inexistent de l'arbre: un fill d'una fulla).
Considereu l'eficiència de l'algorisme de cerca en un arbre equilibrat (un arbre en què els nodes es distribueixen de manera més o menys uniforme). Aleshores, l'eficiència de la cerca serà O(log(n)) i el logaritme de base 2. Vegeu: si hi ha n elements en un arbre equilibrat, això significa que hi haurà log(n) nivells de base 2 de l'arbre. I a la recerca, d'un pas del cicle, baixes un nivell.
inserir
Si heu entès l'essència de la cerca, no us serà difícil entendre la inserció. Només cal que baixeu a la fulla de l'arbre (segons les regles de descendència descrites a la cerca) i esdevingui el seu descendent, a l'esquerra o a la dreta, segons la clau. Implementació:
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;
}
}
}
}
}
En aquest cas, a més del node actual, cal emmagatzemar informació sobre el pare del node actual. Quan el corrent esdevé nul, la variable pare contindrà el full que necessitem.
L'eficiència d'inserció serà, òbviament, la mateixa que la de la cerca - O(log(n)).
Esborrat
La supressió és l'operació més complexa que caldrà fer amb un arbre. Està clar que primer caldrà trobar l'element que anem a eliminar. Però llavors què? Si simplement posem la seva referència a null, perdrem informació sobre el subarbre l'arrel del qual és aquest node. Els mètodes d'eliminació d'arbres es divideixen en tres casos.
Primer cas. El node que s'ha d'eliminar no té fills.
Si el node que s'ha d'esborrar no té fills, vol dir que és una fulla. Per tant, simplement podeu establir els camps leftChild o rightChild del seu pare com a nul.
Segon cas. El node que s'ha d'eliminar té un fill
Aquest cas tampoc és gaire difícil. Tornem al nostre exemple. Suposem que hem d'esborrar un element amb la clau 14. Estigueu d'acord que com que és el fill correcte d'un node amb la clau 10, qualsevol dels seus descendents (en aquest cas, el correcte) tindrà una clau superior a 10, de manera que pot "tallar" fàcilment de l'arbre i connectar el pare directament al fill del node que s'està suprimint, és a dir. connectar el node amb la clau 10 al node 13. La situació seria similar si haguéssim de suprimir un node que és el fill esquerre del seu pare. Penseu-ho per vosaltres mateixos: una analogia exacta.
Tercer cas. Node té dos fills
El cas més difícil. Fem una ullada a un nou exemple.
Busca un successor
Suposem que hem de treure el node amb la clau 25. Qui posarem al seu lloc? Un dels seus seguidors (descendents o descendents de descendents) ha de ser successor(el que ocuparà el lloc del node eliminat).
Com saps qui hauria de ser el successor? Intuïtivament, aquest és el node de l'arbre la clau del qual és la següent més gran del node que s'elimina. L'algorisme és el següent. Cal anar al seu fill dret (sempre al dret, perquè ja es va dir que la clau del successor és més gran que la clau del node que s'esborra), i després passar per la cadena de fills esquerres d'aquesta dreta. nen. En l'exemple, hem d'anar al node amb la clau 35, i després baixar per la cadena dels seus fills esquerres fins a la fulla; en aquest cas, aquesta cadena consta només del node amb la clau 30. En sentit estricte, estem buscant el node més petit del conjunt de nodes més gran que el node desitjat.
Codi del mètode de cerca successor:
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;
}
El codi complet del mètode d'eliminació:
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;
}
La complexitat es pot aproximar a O(log(n)).
Trobar el màxim/mínim en un arbre
Òbviament, com trobar el valor mínim / màxim a l'arbre: heu de passar seqüencialment per la cadena d'elements esquerre / dret de l'arbre, respectivament; quan arribeu a la fulla, serà l'element mínim/màxim.
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;
}
Complexitat - O(log(n))
Bypass simètric
La travessia és una visita a cada node de l'arbre per fer-hi alguna cosa.
Algorisme de recorregut simètric recursiu:
- Feu una acció al nen esquerre
- Fes una acció amb tu mateix
- Feu una acció sobre el nen adequat
Codi:
public void inOrder(Node<T> current) {
if (current != null) {
inOrder(current.getLeftChild());
System.out.println(current.getData() + " ");//Здесь может быть все, что угодно
inOrder(current.getRightChild());
}
}
Conclusió
Per fi! Si no he explicat alguna cosa o tinc cap comentari, estic esperant als comentaris. Com s'havia promès, aquí teniu el codi complet.
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
Degeneració a O(n)
Molts de vosaltres potser us heu adonat: què passa si feu que l'arbre es desequilibri? Per exemple, poseu nodes a l'arbre amb claus creixents: 1,2,3,4,5,6... Aleshores, l'arbre recordarà una mica una llista enllaçada. I sí, l'arbre perdrà la seva estructura d'arbre i, per tant, l'eficiència de l'accés a les dades. La complexitat de les operacions de cerca, inserció i supressió serà la mateixa que la d'una llista enllaçada: O(n). Aquest és un dels desavantatges més importants, al meu entendre, dels arbres binaris.
Només els usuaris registrats poden participar en l'enquesta. si us plau.
Fa molt de temps que no estic a Habré i m'agradaria saber quins articles sobre quins temes t'agradaria veure més?
-
Estructures de dades
-
Algorismes (DP, recursivitat, compressió de dades, etc.)
-
Aplicació d'estructures de dades i algorismes a la vida real
-
Programació d'aplicacions Android en Java
-
Programació d'aplicacions web Java
Han votat 2 usuaris. 1 usuari es va abstenir.
Font: www.habr.com