Différence entre l'arbre binaire et l'arbre de recherche binaire

Quelqu'un peut-il expliquer la différence entre l' arbre binaire et l' arbre de recherche binaire avec un exemple ?

Arbre binaire: arbre où chaque nœud a jusqu'à deux feuilles

  1
 / \
2   3

Arbre de recherche binaire: utilisé pour la recherche . Un arbre binaire où l'enfant gauche contient uniquement des nœuds avec des valeurs inférieures au nœud parent et où l'enfant droit ne contient que des nœuds avec des valeurs supérieures ou égales au parent.

  2
 / \
1   3

L'arbre binaire est une forme d'arbre spécialisée avec deux enfants (enfant gauche et enfant droit). C'est simplement une représentation des données dans la structure arborescente

L'arbre de recherche binaire (BST) est un type spécial d'arbre binaire qui suit la condition suivante:

1. le nœud enfant gauche est plus petit que son nœud parent
2. le nœud enfant droit est supérieur à son nœud parent

Un arbre binaire est constitué de nœuds, où chaque nœud contient un pointeur "gauche", un pointeur "droit" et un élément de données. Le pointeur "racine" pointe vers le nœud le plus haut de l'arborescence. Les pointeurs gauche et droit pointent récursivement vers de plus petits "sous-arbres" de chaque côté. Un pointeur nul représente un arbre binaire sans élément - l'arbre vide. La définition récursive formelle est: un arbre binaire est soit vide (représenté par un pointeur nul), soit constitué d'un seul nœud, où les pointeurs gauche et droit (définition récursive à venir) pointent chacun vers un arbre binaire.

Un arbre de recherche binaire (BST) ou "arbre binaire ordonné" est un type d'arbre binaire où les nœuds sont disposés dans l'ordre: pour chaque nœud, tous les éléments de sa sous-arborescence gauche sont inférieurs au nœud (<), et tous les éléments dans son sous-arbre droit sont supérieurs au nœud (>).

    5
   / \
  3   6 
 / \   \
1   4   9    

L'arbre ci-dessus est un arbre de recherche binaire - le nœud "racine" est un 5, et ses nœuds de sous-arbre gauche (1, 3, 4) sont <5, et ses nœuds de sous-arbre droit (6, 9) sont> 5. Récursivement, chacun des sous-arbres doit également obéir à la contrainte d'arbre de recherche binaire: dans le sous-arbre (1, 3, 4), le 3 est la racine, le 1 <3 et 4> 3.

Faites attention à la formulation exacte des problèmes - un "arbre de recherche binaire" est différent d'un "arbre binaire".

Comme tout le monde ci-dessus a expliqué la différence entre l'arbre binaire et l'arbre de recherche binaire, j'ajoute simplement comment tester si l'arbre binaire donné est un arbre de recherche binaire.

boolean b = new Sample().isBinarySearchTree(n1, Integer.MIN_VALUE, Integer.MAX_VALUE);
.......
.......
.......
public boolean isBinarySearchTree(TreeNode node, int min, int max)
{

    if(node == null)
    {
        return true;
    }

    boolean left = isBinarySearchTree(node.getLeft(), min, node.getValue());
    boolean right = isBinarySearchTree(node.getRight(), node.getValue(), max);

    return left && right && (node.getValue()<max) && (node.getValue()>=min);

}

J'espère que cela vous aidera. Désolé si je m'éloigne du sujet car je pense qu'il vaut la peine de le mentionner ici.

Binary Tree représente une structure de données composée de nœuds qui ne peuvent avoir que deux références enfants .

L'arbre de recherche binaire ( BST ), d'autre part, est une forme spéciale de structure de données d' arbre binaire où chaque nœud a une valeur comparable, et des enfants de plus petite valeur attachés à gauche et des enfants de plus grande valeur attachés à droite.

Ainsi, tous les BST sont des arbres binaires, mais seuls certains arbres binaires peuvent également être des BST . Notifier que BST est un sous-ensemble de l' arbre binaire .

Ainsi, l' arbre binaire est plus une structure de données générale que l' arbre de recherche binaire . Et vous devez également notifier que l' arbre de recherche binaire est un arbre trié alors qu'il n'y a pas un tel ensemble de règles pour l' arbre binaire générique .

Arbre binaire

A Binary Treequi n'est pas un BST;

         5
       /   \
      /     \
     9       2
    / \     / \
  15   17  19  21

Arbre de recherche binaire (arbre trié)

Un arbre de recherche binaire qui est également un arbre binaire ;

         50
       /    \
      /      \
     25      75
    /  \    /  \
  20    30 70   80

Propriété de nœud d'arbre de recherche binaire

Informez également cela pour tout nœud parent dans le BST ;

• Tous les nœuds de gauche ont une valeur inférieure à la valeur du nœud parent. Dans l'exemple supérieur, les nœuds avec des valeurs {20, 25, 30} qui sont tous situés à gauche ( descendants gauches ) de 50, sont plus petits que 50.

• Tous les nœuds droits ont une valeur supérieure à la valeur du nœud parent. Dans l'exemple supérieur, les nœuds de valeurs {70, 75, 80} qui sont tous situés à droite ( descendants droits ) de 50, sont supérieurs à 50.

Il n'y a pas une telle règle pour le nœud d' arbre binaire . La seule règle pour le nœud d' arbre binaire est d'avoir deux enfants, il s'explique donc lui-même pourquoi il est appelé binaire .

Un arbre de recherche binaire est un type spécial d'arbre binaire qui présente la propriété suivante: pour tout nœud n, la valeur de chaque nœud descendant dans le sous-arbre gauche de n est inférieure à la valeur de n, et la valeur de chaque nœud descendant dans le sous-arbre droit est supérieur à la valeur de n.

Arbre binaire

L'arbre binaire peut être tout ce qui a 2 enfants et 1 parent. Il peut être implémenté sous forme de liste ou de tableau lié, ou avec votre API personnalisée. Une fois que vous commencez à y ajouter des règles plus spécifiques, il devient un arbre plus spécialisé . L'implémentation connue la plus courante consiste à ajouter des nœuds plus petits à gauche et des nœuds plus grands à droite.

Par exemple, un arbre binaire étiqueté de taille 9 et de hauteur 3, avec un nœud racine dont la valeur est 2. L'arbre est déséquilibré et non trié . https://en.wikipedia.org/wiki/Binary_tree

Par exemple, dans l'arbre de gauche, A a les 6 enfants {B, C, D, E, F, G}. Il peut être converti en arbre binaire à droite.

Recherche binaire

La recherche binaire est une technique / algorithme qui est utilisé pour trouver un élément spécifique sur la chaîne de nœuds. La recherche binaire fonctionne sur des tableaux triés .

La recherche binaire compare la valeur cible à l' élément central du tableau; s'ils sont inégaux, la moitié dans laquelle la cible ne peut pas mentir est éliminée et la recherche se poursuit sur la moitié restante jusqu'à ce qu'elle réussisse ou que la moitié restante soit vide. https://en.wikipedia.org/wiki/Binary_search_algorithm

Un arbre représentant la recherche binaire . Le tableau recherché ici est [20, 30, 40, 50, 90, 100], et la valeur cible est 40.

Arbre de recherche binaire

C'est l'une des implémentations de l'arbre binaire. C'est spécialisé pour la recherche .

L'arbre de recherche binaire et les structures de données de l'arbre B sont basés sur la recherche binaire .

Les arbres de recherche binaire (BST), parfois appelés arbres binaires ordonnés ou triés, sont un type particulier de conteneur : les structures de données qui stockent des "éléments" (tels que des nombres, des noms, etc.) en mémoire. https://en.wikipedia.org/wiki/Binary_search_tree

Un arbre de recherche binaire de taille 9 et de profondeur 3, avec 8 à la racine. Les feuilles ne sont pas dessinées.

Et enfin un excellent schéma pour la comparaison des performances des structures de données et des algorithmes bien connus appliqués:

Image prise à partir d' algorithmes (4e édition)

Un arbre binaire est un arbre dont les enfants n'ont jamais plus de deux ans. Un arbre de recherche binaire suit l'invariant selon lequel l'enfant gauche doit avoir une valeur inférieure à la clé du nœud racine, tandis que l'enfant droit doit avoir une valeur supérieure à la clé du nœud racine.

• Arbre de recherche binaire: lorsque la traversée dans l'ordre est effectuée sur l'arbre binaire, vous obtenez des valeurs triées des éléments insérés
• Arbre binaire: aucun ordre de tri n'est trouvé dans aucun type de parcours

Pour vérifier si un arbre binaire donné est un arbre de recherche binaire, voici une approche alternative.

Traverser l'arbre dans le mode inverse (c.-à-d. Enfant gauche -> parent -> enfant droit), stocker les données de nœud traversées dans une variable temporaire permet de dire temp , juste avant de les stocker dans temp , de vérifier si les données du nœud actuel sont plus élevées que les précédentes ou non . Ensuite, décomposez -le, l'arbre n'est pas un arbre de recherche binaire, sinon traversez jusqu'à la fin.

Voici un exemple avec Java:

public static boolean isBinarySearchTree(Tree root)
{
    if(root==null)
        return false;

    isBinarySearchTree(root.left);
    if(tree.data<temp)
        return false;
    else
        temp=tree.data;
    isBinarySearchTree(root.right);
    return true;
}

Conserver la variable de température à l'extérieur

Dans un arbre de recherche binaire, tous les nœuds sont organisés dans un ordre spécifique - les nœuds à gauche d'un nœud racine ont une valeur plus petite que sa racine, et tous les nœuds à droite d'un nœud ont des valeurs supérieures à la valeur du racine.

Un arbre peut être appelé comme arbre binaire si et seulement si le nombre maximal d'enfants de l'un des nœuds est de deux.

Un arbre peut être appelé comme arbre de recherche binaire si et seulement si le nombre maximal d'enfants de l'un des nœuds est de deux et que l'enfant gauche est toujours plus petit que l'enfant droit.