Questions et réponses d'entretien d'arbre binaire les plus courantes [Pour les débutants et les expérimentés]

introduction

Les structures de données sont l'un des concepts les plus fondamentaux de la programmation orientée objet. Pour l'expliquer simplement, une structure de données est une manière particulière d'organiser les données dans un ordinateur afin qu'elles puissent être traitées efficacement. Il existe plusieurs structures de données telles que des piles, des files d'attente et des arborescences qui ont leurs propres propriétés uniques.

Les arbres nous permettent d'organiser les données de manière hiérarchique. Une telle structure de données est très différente des structures de données linéaires telles que les listes chaînées ou les tableaux. Un arbre est constitué de nœuds qui transportent des informations.

Un arbre binaire est un type spécial d'arbre qui ne peut avoir que deux enfants. Cela signifie qu'un nœud particulier dans un arbre binaire peut n'avoir aucun enfant, un enfant ou deux enfants mais pas plus. Un arbre binaire est une structure de données importante qui peut nous permettre de résoudre des problèmes difficiles et de construire des codes complexes.

Si vous postulez pour un emploi en tant que développeur Java ou ingénieur logiciel, votre entretien peut contenir plusieurs questions tournant autour de ce concept. Souvent, les candidats ont du mal à répondre aux questions basées sur les arbres binaires, les arbres de recherche binaires et les programmes associés. Dans cet article, nous explorerons certaines des questions d'entretien les plus fréquemment posées concernant les arbres binaires. Cet article vous aidera à mieux comprendre le concept et à vous préparer pour décrocher le job de vos rêves !

Principales questions et réponses d'entretien d'arbre binaire

La section suivante contient un catalogue de questions et leurs réponses attendues basées sur le concept d'arbre binaire.

1) Qu'est-ce qu'un nœud feuille ?

Tout nœud d'un arbre binaire ou d'un arbre qui n'a pas d'enfant est appelé nœud feuille.

2) Qu'est-ce qu'un nœud racine ?

Le premier nœud ou le nœud supérieur d'un arbre est appelé le nœud racine.

3) Comment trouvez-vous l'ancêtre commun le plus bas (LCA) d'un arbre binaire en Java ?

Considérons deux nœuds n1 et n2 faisant partie d'un arbre binaire.

L'ancêtre commun le plus bas (LCA) de n1 et n2 est l'ancêtre partagé de n1 et n2 qui est situé le plus loin de la racine.

Vous pouvez suivre la méthode suivante pour trouver le LCA.

1. a) Trouvez un chemin du nœud racine à n1 et stockez-le dans un tableau.
2. b) Trouvez un chemin du nœud racine à n2 et stockez-le dans un tableau.
3. c) Parcourez les deux chemins jusqu'à ce que la valeur soit la même dans les deux tableaux.

4) Comment vérifier si un arbre binaire donné est un sous-arbre d'un autre arbre binaire ?

Considérons que nous avons un arbre binaire T. Nous voulons maintenant vérifier si un arbre binaire S est un sous-arbre de T.

Pour ce faire, essayez d'abord de vérifier si vous trouvez un nœud dans T qui est également dans S.

Une fois que vous avez trouvé ce nœud commun, vérifiez si les nœuds suivants font également partie de S.

Si oui, nous pouvons dire sans risque que S est un sous-arbre de T.

Doit lire: Idées et sujets de projet de structure de données

5) Comment trouve-t-on la distance entre deux nœuds dans un arbre binaire ?

Considérons deux nœuds n1 et n2 qui font partie d'un arbre binaire.

La distance entre n1 et n2 est égale au nombre minimum d'arêtes à traverser pour passer d'un nœud à l'autre.

Il est important de noter que vous parcourez la distance la plus courte entre les nœuds.

6) Qu'est-ce qu'un arbre de recherche binaire ?

Un arbre binaire de recherche (BST) est un type spécial d'arbre binaire dans lequel chaque nœud interne contient une clé. Pour un arbre de recherche binaire, la règle est :

1. a) Un nœud peut avoir une clé supérieure à toutes les clés du sous-arbre gauche du nœud.
2. b) Un nœud peut avoir une clé plus petite que toutes les clés du sous-arbre droit du nœud.

Ainsi, si n1 est un nœud qui a une clé 8, alors chaque nœud du sous-arbre gauche de n1 contiendra des clés inférieures à 8, et chaque nœud du sous-arbre droit de n1 contiendra des clés supérieures à 8.

7) Qu'est-ce qu'un arbre auto-équilibré ?

Les arbres de recherche binaires auto-équilibrés conservent automatiquement leur hauteur aussi petite que possible lorsque des opérations telles que l'insertion et la suppression ont lieu.

Pour qu'un BST soit auto-équilibré, il est important qu'il suive systématiquement les règles du BST afin que le sous-arbre de gauche ait des clés de valeur inférieure tandis que le sous-arbre de droite a des clés de valeur élevée.

Cela se fait à l'aide de deux opérations :

– Rotation à gauche

– Rotation à droite

8) Qu'est-ce qu'un arbre AVL ?

L'arbre AVL porte le nom de ses inventeurs : Adelson, Velski et Landis. Un arbre AVL est un arbre binaire auto-équilibré qui vérifie la hauteur de son sous-arbre gauche et de son sous-arbre droit et s'assure que la différence n'est pas supérieure à 1. Cette différence est appelée facteur d'équilibre.

Ainsi, BalanceFactor = hauteur (sous-arbre gauche) - hauteur (sous-arbre droit)

Si le facteur d'équilibre est supérieur à 1, l'arbre est équilibré en utilisant certaines des techniques suivantes :

– Rotation à gauche

– Rotation à droite

– Rotation gauche-droite

– Rotation droite-droite

A lire également : Trier dans la structure des données

9) Comment convertir un arbre binaire en arbre binaire de recherche en Java ?

La principale différence entre un arbre binaire et un arbre de recherche binaire est que le BST suit que le sous-arbre de gauche doit avoir des valeurs de clé inférieures et que le sous-arbre de droite doit avoir une règle de valeurs de clé plus élevées. Cela peut être fait en utilisant une série de techniques de traversée comme suit :

1. Créer un tableau temporaire qui stocke le parcours dans l'ordre de l'arbre
2. Triez le tableau temporaire. Vous pouvez utiliser n'importe quel algorithme de tri ici.
3. Effectuez à nouveau un parcours dans l'ordre de l'arbre.
4. Copiez les éléments du tableau un par un dans chaque nœud de l'arbre.

10) Comment supprimez-vous un nœud d'un arbre de recherche binaire en Java ?

L'opération de suppression d'une BST peut être délicate car ses propriétés doivent être conservées après l'opération. Voici un aperçu des trois cas possibles :

1. Le nœud à supprimer est un nœud feuille.
   Supprimez simplement le nœud.
2. Le nœud à supprimer a un enfant.

Dans ce cas, copiez l'enfant sur le nœud et supprimez l'enfant.

1. Le nœud à supprimer a deux enfants.

Dans ce cas, recherchez le successeur dans l'ordre du nœud. Vous pouvez ensuite copier son contenu sur le nœud et supprimer le successeur de l'ordre.

11) Qu'est-ce que la structure de données de l'arbre rouge-noir ?

L'arbre rouge-noir est un type spécial d'arbre auto-équilibré qui a les propriétés suivantes :

1. Chaque nœud a une couleur rouge ou noire.
2. La racine est toujours noire.
3. Un nœud rouge ne peut pas avoir de parent rouge ou d'enfant rouge.
4. Chaque chemin du nœud racine à un nœud NULL a le même nombre de nœuds noirs.

Doit lire: Idées et sujets de projet de structure de données

12) Comment trouve-t-on si deux arbres sont identiques ?

Deux arbres binaires sont identiques s'ils ont les mêmes données et la même disposition. Cela peut être fait en parcourant les deux arbres et en comparant leurs données et leurs arrangements.

Voici l'algorithme qui peut nous permettre de faire cela :

1. Vérifier les données du nœud racine (données tree1 ==données tree2)
2. Vérifiez le sous-arbre gauche de manière récursive. call sameTree( tree1-> left subtree, tree2-> left subtree)
3. De même, vérifiez le sous-arbre droit
4. si a,b,c sont vrais, retourne1

Paiement : Types d'arbre binaire

Dernières pensées

Dans cet article, nous avons exploré certaines des questions d'entretien d'arbre de recherche binaire les plus fréquemment posées. En savoir plus sur les structures de données peut vous aider à mieux comprendre la logique et la programmation. Vous pouvez essayer de regarder les exemples mentionnés dans cet article et vous entraîner en changeant les valeurs pour construire vos fondamentaux. Avec un peu de pratique, vous serez en excellente position pour réussir votre entretien.

Si vous êtes curieux d'en savoir plus sur la science des données, consultez le programme Executive PG en science des données de IIIT-B & upGrad qui est créé pour les professionnels en activité et propose plus de 10 études de cas et projets, des ateliers pratiques, un mentorat avec des experts de l'industrie, 1 -on-1 avec des mentors de l'industrie, plus de 400 heures d'apprentissage et d'aide à l'emploi avec les meilleures entreprises.