nième plus petit élément d'un BST

Question

un BST (arbre de recherche binaire) T est donné. comment trouver le nième plus petit élément de T?

Answer 1

Un arbre de recherche binaire est efficacement trié, il suffit donc de passer par l'arbre dans l'ordre et d'arriver à la énième place. Si l'arbre est complètement équilibré, vous pouvez calculer l'endroit où vous pouvez aller.

Answer 2

Si l'arbre de recherche binaire n'est pas complètement équilibré, alors vous devez effectuer une recherche récursive pour trouver le nième élément le plus petit. Cela peut être considérablement accéléré en faisant en sorte que chaque nœud stocke le nombre de sous-nœuds pointés par chacun de ses pointeurs de branchement, transformant ainsi la recherche en une binaire. Toutefois, cela ajoute un surcoût sur les mises à jour de l'arborescence car chaque insertion ou suppression nécessite désormais une traversée feuille à racine pour mettre à jour les comptes de nœud.

Alternativement, vous pouvez garder l'arbre équilibré, et utilisez la réponse ci-dessus.