interview java-arbre rouge-noir

Tout d'abord, jetons un coup d'œil à la structure de l'arbre rouge-noir, comme le montre la figure :

(Partage de vidéos d'apprentissage : vidéo pédagogique java)

Les caractéristiques structurelles de l'arbre rouge-noir :

(1) Chaque nœud est soit noir, soit rouge.
(2) Le nœud racine est noir.
(3) Chaque nœud feuille (NIL) est noir. [Remarque : les nœuds feuilles ici font référence aux nœuds feuilles qui sont vides (NIL ou NULL) ! ]
(4) Si un nœud est rouge, ses nœuds enfants doivent être noirs.
(5) Tous les chemins d'un nœud aux nœuds descendants du nœud contiennent le même nombre de nœuds noirs.

Pourquoi utiliser des arbres rouge-noir ?

1. Tout d'abord, les arbres rouge-noir ne remplissent pas les conditions d'équilibre des arbres AVL, c'est-à-dire des arbres de recherche binaires dans lesquels les hauteurs du sous-arbre gauche et du sous-arbre droit de chaque nœud diffèrent d'au plus 1. Cependant, il est proposé d'ajouter des couleurs aux nœuds. L'arbre rouge-noir utilise un équilibre non strict pour réduire le nombre de rotations lors de l'ajout ou de la suppression de nœuds. Tout déséquilibre sera résolu en trois rotations, tandis que AVL est un arbre strictement équilibré. ainsi lors de l'ajout ou de la suppression de nœuds, lorsqu'il s'agit de nœuds, selon la situation, le nombre de rotations est supérieur à celui de l'arbre rouge-noir. Par conséquent, l'efficacité d'insertion des arbres rouge-noir est plus élevée

(Recommandations pour des questions d'entretien plus connexes : questions et réponses d'entretien Java)

2. peut effectuer O (La complexité temporelle de log2 (n)) est utilisée pour effectuer des opérations de recherche, d'insertion et de suppression

3. En termes simples, l'arbre rouge-noir sert à résoudre les lacunes de l'arbre de recherche binaire , car l'arbre de recherche binaire dégénérera dans certains cas en une structure linéaire.

Comparaison et sélection de l'arbre rouge-noir et de l'arbre équilibré

1. La structure arborescente équilibrée est plus intuitive et les performances de lecture sont supérieures à celles de l'arbre rouge-noir ; l'ajout et la suppression de nœuds pour rétablir l'équilibre ne sont pas aussi bons que ceux de l'arbre rouge-noir Arbre noir
2. Les performances de lecture ne sont pas aussi bonnes que celles de l'arbre équilibré pour restaurer l'équilibre ; est pire qu'un arbre équilibré

Scénarios d'utilisation de l'arbre rouge-noir :

TreeMap, TreeSet et HashMap après JDK1.8 utilisent des arbres rouge-noir dans la couche inférieure.

Recommandations associées : Tutoriel d'introduction à Java

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!