Quelles sont les caractéristiques d’un arbre binaire équilibré ?

Les caractéristiques d'un arbre binaire équilibré sont : 1. Un nœud non-feuille a au plus deux nœuds enfants 2. La valeur d'un nœud non-feuille est supérieure au nœud enfant gauche et inférieure à la valeur d'un nœud non-feuille. nœud enfant droit ; 3. Le nombre de niveaux sur les côtés gauche et droit de l’arborescence est le même et sera supérieur à 4. Il n’y a pas de nœuds en double avec des valeurs égales.

Caractéristiques des arbres binaires équilibrés :

(1) Les nœuds non-feuilles ont au plus deux nœuds enfants ;

(2) La valeur du nœud non-feuille est supérieure à celle du nœud enfant gauche et inférieure à celle du nœud enfant droit

(3) La différence dans le nombre de niveaux à gauche et ; les côtés droits de l'arbre ne seront pas supérieurs à 1 ;

(4) Il n'y a pas de nœuds en double avec des valeurs égales ;

Le concept d'arbre binaire équilibré

L'arbre binaire équilibré est une structure de données d'un arbre binaire basée sur la stratégie de dichotomie pour améliorer la vitesse de recherche de données ;

Caractéristiques :

Le L'arbre binaire équilibré utilise la pensée dichotomique pour assembler les données dans une structure arborescente selon des règles. Cette structure arborescente est utilisée pour réduire la récupération de données non pertinentes. Améliore considérablement la vitesse de récupération de la structure des données d'un arbre binaire équilibré ; les règles suivantes :

(1) Les nœuds non-feuilles ne peuvent autoriser que jusqu'à deux nœuds enfants.

(2) La règle de distribution des données de chaque nœud non-feuille est que le nœud enfant de gauche est plus petit que la valeur du nœud actuel et que le nœud enfant de droite est supérieur à la valeur de le nœud actuel (la valeur ici est basée sur ses propres règles d'algorithme, Par exemple, la valeur de hachage

La structure hiérarchique de l'arbre équilibré : Parce que les performances des requêtes de l'arbre binaire équilibré sont inversement proportionnelles au nœud actuel) ; Au niveau de l'arbre (h hauteur), plus la valeur h est petite, plus la requête est rapide. Afin de garantir que les données aux extrémités gauche et droite de la structure arborescente équilibrent et réduisent grossièrement la difficulté de requête d'un arbre binaire, un Le mécanisme d'algorithme est généralement utilisé pour atteindre l'équilibre de la structure de données des nœuds. Des exemples de tels algorithmes incluent Treap et les arbres rouge-noir. L'utilisation d'un arbre binaire équilibré peut garantir que les niveaux de nœuds sur les côtés gauche et droit des données ne diffèrent pas. . Supérieur à 1. Cela empêche la structure arborescente de devenir une liste chaînée linéaire en raison de l'augmentation des suppressions, ce qui affecte l'efficacité des requêtes et la vitesse de recherche des données tout en garantissant que l'équilibre des données est proche de celui de la recherche binaire

Pour plus de connaissances connexes, veuillez visiter le

site Web PHP chinois  ! !

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!