Comment créer un binaire arbre de recherche à partir d'un tableau
Le mardi j'aime discuter des moyens que vous pouvez préparer à une entrevue de codage, et aujourd'hui, je vais discuter de la façon de créer un arbre de recherche binaire d'un tableau. En ce qui concerne les entretiens d'embauche des développeurs, des questions concernant les structures de données sont très populaires et sont donc importantes pour préparer des arbres de recherche for.Binary sont l'une de mes structures de données favorites pour travailler avec parce qu'ils sont incroyablement efficaces, si elle est gérée correctement, et ils sont aussi simple à comprendre.
Commençons d'abord par établir des règles pour les arbres binaires de recherche:
- Un nœud parent a, au plus, 2 nœuds enfants.
- Le nœud enfant gauche est toujours inférieur au nœud parent.
- Le nœud enfant droit est toujours supérieur ou égal au nœud parent.
Il y a quelques semaines, je couvrais comment fonctionne la recherche binaire. alors s'il vous plaît ne hésitez pas à faire référence à ce poste pour la partie de recherche de l'algorithme. Dans ce guide, je vais discuter de la façon dont vous pouvez créer un arbre de recherche binaire à partir d'un tableau de données.
Voici le tableau que nous allons utiliser pour ce tutoriel:
Ceci est un tableau d'entiers de base constitué de sept valeurs qui sont dans l'ordre trié.
Créer un binaire Recherche Arbre
La première valeur du tableau est 10, donc la première étape dans la construction de l'arbre sera de faire 10 le nœud racine, comme indiqué ici:
Avec le jeu de nœud racine, toutes les valeurs restantes seront les enfants de ce noeud. Référençant nos règles depuis le début de ce post, nous savons que les nœuds enfants seront désignés comme les nœuds enfants droite ou à gauche en fonction de leur valeur. Par conséquent, la première étape que nous allons prendre pour ajouter 7 à l'arbre sera de le comparer au nœud racine:
Si le 7 est inférieur à 10, il deviendra le nœud enfant gauche. Si le 7 est supérieur ou égal à 10, il se déplace vers la droite. Puisque nous savons que le 7 est inférieur à 10 l'on désigne comme le noeud enfant gauche, comme indiqué ici.
Récursive effectuer des comparaisons pour chaque élément
Sur le même modèle, nous effectuons la même comparaison avec la valeur 14 dans le tableau. En comparant la valeur de 14 au nœud racine de 10, nous savons que 14 est l'enfant droit.
Faire notre chemin à travers l'ensemble, nous arrivons à la 20. Nous allons commencer par comparer le tableau à 10, il est supérieur. Nous passons donc à droite et à comparer avec 14, il est supérieur à 14 et 14 n'a pas d'enfant à droite, donc nous faire 20 l'enfant droit de 14.
Notre arbre vient bien le long. Maintenant, nous avons la valeur 1. En suivant le même schéma que les autres valeurs que nous comparerons 1 à 10, passez à la gauche et le comparer avec 7, et enfin faire 1 l'enfant gauche du noeud 7.
Avec la valeur 5 on le compare à la 10. Depuis 5 est inférieur à 10 on traverse à gauche et de le comparer avec 7. Puisque nous savons que 5 est inférieur à 7, nous continuons sur l'arbre et comparer les 5 à la valeur 1. Avec 1 ayant pas de nœuds enfants et 5 étant supérieur à 1, nous savons faire 5 l'enfant droit du nœud 1.
Enfin, nous allons insérer la valeur 8 dans l'arbre. 8 étant inférieur à 10 on passe à la gauche et de le comparer avec 7. 8 est supérieur à 7, donc nous passons à droite et à compléter l'arbre faisant 8 l'enfant droit de 7.
J'espère que vous apprécierez l'élégance simple des arbres binaires de recherche. Comme tant de sujets dans la programmation et dans la vie, la force des arbres binaires de recherche vient de leur capacité à permettre aux données d'être divisées en petits composants connectés. A partir de ce moment-là, nous pouvons travailler avec les données complètes établies de manière organisée. En faisant référence au tutoriel arbre de recherche binaire j'ai donné précédemment, nous pourrions prendre l'arbre que nous avons construit dans ce guide et une recherche efficace au travers de trouver un élément qui avait déjà été dans le tableau.
Les problèmes potentiels avec les arbres binaires de recherche
Aussi grand que les arbres binaires de recherche sont, il y a quelques mises en garde à garder à l'esprit.
Si nous avons essayé d'exécuter l'algorithme d'arbre de recherche binaire sur cet arbre, il effectuerait exactement la même chose que si nous simplement itéré le tableau jusqu'à ce que nous avons trouvé la valeur que nous recherchions. La force de recherche binaire vient d'être en mesure de filtrer rapidement les valeurs inutiles. Quand un arbre est déséquilibré, en particulier comme le type d'arbre qui résulterait d'un tableau trié, il ne donnera pas les mêmes avantages comme un arbre équilibré. Vous pouvez le comparer revenir à la sortie finale que notre tableau non trié généré ici.
Tout cela signifie qu'il est essentiel de comprendre les données que vous travaillez avec lorsque vous créez un arbre de recherche binaire. Vous pouvez intégrer des sous-routines, comme randomiser un tableau avant de créer un arbre de recherche binaire pour l'équilibrer. À l'avenir, je vais couvrir aussi des sujets liés à AVL et Red arbres noirs. Ces types d'algorithmes assurent qu'un arbre est conserve les caractéristiques de l'équilibre approprié.
J'espère que cela a été un guide utile pour comprendre comment créer pratiquement un arbre binaire de recherche à partir d'une structure de données de tableau. Bonne chance avec l'interview!