Prélude
Cet article concerne les arbres de recherche binaires. J'ai récemment écrit un article sur Là je n'ai pas vraiment prêté attention aux arbres binaires, car les méthodes de recherche, d'insertion, de suppression n'étaient pas pertinentes. Maintenant, j'ai décidé d'écrire un article sur les arbres. On va peut-être commencer.
Un arbre est une structure de données constituée de nœuds reliés par des arêtes. On peut dire qu'un arbre est un cas particulier de graphe. Voici un exemple d'arborescence :
Ceci n'est pas un arbre de recherche binaire ! Tout est sous la coupe !
Vocabulaire
racine
Racine d'arbre est le nœud le plus haut. Dans l'exemple, il s'agit du nœud A. Dans l'arbre, un seul chemin peut mener de la racine à n'importe quel autre nœud ! En fait, tout nœud peut être considéré comme la racine du sous-arbre correspondant à ce nœud.
Parents/progéniture
Tous les nœuds, à l'exception de la racine, ont exactement une arête menant à un autre nœud. Le nœud au-dessus du nœud actuel est appelé parent ce nœud. Un nœud situé en dessous du nœud actuel et connecté à celui-ci est appelé descendant ce nœud. Prenons un exemple. Prenez le nœud B, son parent sera alors le nœud A et ses enfants seront les nœuds D, E et F.
Feuille
Un nœud qui n'a pas d'enfant est appelé une feuille de l'arbre. Dans l'exemple, les nœuds D, E, F, G, I, J, K seront des feuilles.
C'est la terminologie de base. D'autres concepts seront abordés ultérieurement. Ainsi, un arbre binaire est un arbre dans lequel chaque nœud n'aura pas plus de deux enfants. Comme vous l'avez deviné, l'arbre de l'exemple ne sera pas binaire, car les nœuds B et H ont plus de deux enfants. Voici un exemple d'arbre binaire :
Les nœuds de l'arbre peuvent contenir n'importe quelle information. Un arbre de recherche binaire est un arbre binaire qui a les propriétés suivantes :
- Les sous-arbres gauche et droit sont des arbres de recherche binaires.
- Tous les nœuds du sous-arbre gauche d'un nœud arbitraire X ont des valeurs de clé de données inférieures à la valeur de clé de données du nœud X lui-même.
- Tous les nœuds du sous-arbre droit d'un nœud arbitraire X ont des valeurs de clé de données supérieures ou égales à la valeur de la clé de données du nœud X lui-même.
clé - une caractéristique du nœud (par exemple, un nombre). La clé est nécessaire pour pouvoir trouver l'élément de l'arbre auquel cette clé correspond. Exemple d'arbre de recherche binaire :
arborescence
Au fur et à mesure, j'inclurai quelques morceaux de code (peut-être incomplets) afin d'améliorer votre compréhension. Le code complet sera à la fin de l'article.
L'arbre est composé de nœuds. Structure du nœud :
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;
}
//...остальные методы узла
}
Chaque nœud a deux enfants (il est tout à fait possible que les enfants leftChild et/ou rightChild soient nuls). Vous avez probablement compris que dans ce cas, les données numériques sont les données stockées dans le nœud ; clé - clé de nœud.
Nous avons compris le nœud, parlons maintenant des problèmes urgents concernant les arbres. Ici et ci-dessous, le mot "arbre" signifiera le concept d'arbre de recherche binaire. Arborescence binaire :
public class BinaryTree<T> {
private Node<T> root;
//методы дерева
}
En tant que champ de classe, nous n'avons besoin que de la racine de l'arbre, car à partir de la racine, en utilisant les méthodes getLeftChild() et getRightChild(), vous pouvez accéder à n'importe quel nœud de l'arbre.
Algorithmes d'arborescence
rechercher
Disons que vous avez un arbre construit. Comment trouver un élément avec la clé clé? Vous devez vous déplacer séquentiellement de la racine vers le bas de l'arborescence et comparer la valeur de la clé avec la clé du nœud suivant : si la clé est inférieure à la clé du nœud suivant, puis passez au descendant gauche du nœud, si plus - à droite, si les clés sont égales - le nœud souhaité est trouvé ! Code pertinent :
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 courant devient nul, alors l'itération a atteint la fin de l'arbre (à un niveau conceptuel, vous êtes dans un endroit inexistant dans l'arbre - un enfant d'une feuille).
Considérons l'efficacité de l'algorithme de recherche sur un arbre équilibré (un arbre dans lequel les nœuds sont répartis plus ou moins uniformément). Alors l'efficacité de la recherche sera O(log(n)), et le logarithme de base 2. Voir : s'il y a n éléments dans un arbre équilibré, cela signifie qu'il y aura log(n) niveaux de base 2 de l'arbre. Et dans la recherche, pour une étape du cycle, vous descendez d'un niveau.
insérer
Si vous avez saisi l'essence de la recherche, il ne vous sera pas difficile de comprendre l'insertion. Il vous suffit de descendre jusqu'à la feuille de l'arbre (selon les règles de descendance décrites dans la recherche) et de devenir son descendant - gauche ou droite, selon la clé. Mise en œuvre:
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;
}
}
}
}
}
Dans ce cas, en plus du nœud courant, il est nécessaire de stocker des informations sur le parent du nœud courant. Lorsque courant devient nul, la variable parent contiendra la feuille dont nous avons besoin.
L'efficacité d'insertion sera évidemment la même que celle de la recherche - O(log(n)).
Enlèvement
La suppression est l'opération la plus complexe qui devra être effectuée avec un arbre. Il est clair qu'il faudra d'abord trouver l'élément que l'on va supprimer. Mais alors quoi ? Si nous définissons simplement sa référence sur null, nous perdrons des informations sur le sous-arbre dont la racine est ce nœud. Les méthodes d'abattage d'arbres sont divisées en trois cas.
Premier cas. Le nœud à supprimer n'a pas d'enfant.
Si le nœud à supprimer n'a pas d'enfant, cela signifie qu'il s'agit d'une feuille. Par conséquent, vous pouvez simplement définir les champs leftChild ou rightChild de son parent sur null.
Deuxième cas. Le nœud à supprimer a un enfant
Ce cas n'est pas non plus très difficile. Revenons à notre exemple. Supposons que nous devions supprimer un élément avec la clé 14. Convenez que puisqu'il s'agit du bon enfant d'un nœud avec la clé 10, alors l'un de ses descendants (dans ce cas, le bon) aura une clé supérieure à 10, donc vous peut facilement le "couper" de l'arborescence et connecter le parent directement à l'enfant du nœud en cours de suppression, c'est-à-dire connectez le nœud avec la clé 10 au nœud 13. La situation serait similaire si nous devions supprimer un nœud qui est l'enfant gauche de son parent. Pensez-y par vous-même - une analogie exacte.
Troisième cas. Node a deux enfants
Le cas le plus difficile. Prenons un nouvel exemple.
Rechercher un successeur
Disons que nous devons supprimer le nœud avec la clé 25. Qui allons-nous mettre à sa place ? Un de ses successeurs (descendants ou descendants de descendants) doit devenir successeur(celui qui prendra la place du nœud supprimé).
Comment savez-vous qui devrait être le successeur? Intuitivement, il s'agit du nœud de l'arborescence dont la clé est la plus grande suivante à partir du nœud supprimé. L'algorithme est le suivant. Il faut aller à son fils droit (toujours à celui de droite, car il a déjà été dit que la clé du successeur est supérieure à la clé du nœud à supprimer), puis passer par la chaîne des fils gauches de ce droit enfant. Dans l'exemple, nous devons aller au nœud avec la clé 35, puis descendre la chaîne de ses enfants gauches jusqu'à la feuille - dans ce cas, cette chaîne se compose uniquement du nœud avec la clé 30. Strictement parlant, nous recherchons le plus petit nœud de l'ensemble de nœuds supérieur au nœud souhaité.
Code de la méthode de recherche du successeur :
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;
}
Le code complet de la méthode delete :
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 complexité peut être approchée à O(log(n)).
Trouver le maximum/minimum dans un arbre
Évidemment, comment trouver la valeur minimale / maximale dans l'arbre - vous devez parcourir séquentiellement la chaîne d'éléments gauche / droite de l'arbre, respectivement; lorsque vous arriverez à la feuille, ce sera l'élément minimum/maximum.
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;
}
Complexité - O(log(n))
By-pass symétrique
La traversée est une visite à chaque nœud de l'arbre afin d'en faire quelque chose.
Algorithme de parcours symétrique récursif :
- Faire une action sur l'enfant de gauche
- Faites une action avec vous-même
- Faire une action sur le bon enfant
Code:
public void inOrder(Node<T> current) {
if (current != null) {
inOrder(current.getLeftChild());
System.out.println(current.getData() + " ");//Здесь может быть все, что угодно
inOrder(current.getRightChild());
}
}
Conclusion
Enfin! Si je n'ai pas expliqué quelque chose ou si j'ai des commentaires, alors j'attends dans les commentaires. Comme promis, voici le code 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
Dégénérescence en O(n)
Beaucoup d'entre vous l'ont peut-être remarqué : et si vous déséquilibriez l'arbre ? Par exemple, placez des nœuds dans l'arbre avec des clés croissantes : 1,2,3,4,5,6... L'arbre ressemblera alors un peu à une liste chaînée. Et oui, l'arbre perdra sa structure arborescente, et donc l'efficacité de l'accès aux données. La complexité des opérations de recherche, d'insertion et de suppression deviendra la même que celle d'une liste chaînée : O(n). C'est l'un des inconvénients les plus importants, à mon avis, des arbres binaires.
Seuls les utilisateurs enregistrés peuvent participer à l'enquête. s'il te plait.
Je ne suis pas venu sur Habré depuis assez longtemps, et j'aimerais savoir quels articles sur quels sujets aimeriez-vous voir davantage ?
-
Structures de données
-
Algorithmes (DP, récursivité, compression de données, etc.)
-
Application des structures de données et des algorithmes dans la vie réelle
-
Programmation d'applications Android en Java
-
Programmation d'applications Web Java
2 utilisateurs ont voté. 1 utilisateur s'est abstenu.
Source : www.habr.com