Arbre binaire vs arbre de recherche binaire Big oh Analyse

Question

Un arbre de recherche binaire équilibré vous aiderait-il à accomplir la tâche suivante dans un temps plus grand et plus rapide qu'un arbre binaire équilibré?

Création d'une liste de tous les éléments de l'arbre qui sont plus petits à une certaine valeur v.

À mon avis non parce que si toutes les valeurs de la BST sont plus petits que v. Ensuite, vous devrez visiter chaque node et ce serait O (n) ce qui n'est pas mieux qu'un arbre binaire.

Ai-je raison?

Answer 1

À mon avis non parce que si toutes les valeurs de la BST sont plus petits que v. Ensuite, vous devrez visiter chaque nœud et qui serait O (n) qui n'est pas mieux qu'un binaire arbre.

Ai-je raison?

Vous êtes. Notez cependant que pour tous les buts pratiques est préférable d'utiliser BST, car avec l'arbre binaire "simple" vous devez toujours visiter tous les nœuds afin de trouver ceux plus petits que v, tandis que dans BST avec traversée en ordre vous examinez seulement ceux plus petit que v.