Kth Smallest Element in a BST
On vous donne un arbre binaire de recherche sous forme de tableau root en ordre de tas : la racine se trouve à l’indice 0, les enfants de l’indice i se trouvent aux indices 2*i+1 (à gauche) et 2*i+2 (à droite), et -1 indique un emplacement vide. Le tableau peut se terminer par des entrées -1 supplémentaires. À chaque nœud, le sous-arbre gauche ne contient que des valeurs plus petites et le sous-arbre droit, uniquement des valeurs plus grandes.
Renvoyez la k-ième plus petite valeur de l’arbre, en comptant à partir de 1.
Fonction
- rootinteger-array
- l’arbre binaire de recherche par niveau, avec -1 pour une place vide
- kinteger
- la position à trouver dans l’ordre croissant, en commençant à 1
- Renvoieinteger
- la k-ième plus petite valeur dans l’arbre
Contraintes
1 ≤ root.length ≤ 32767- Chaque
root[i]vaut-1ou une valeur telle que0 ≤ root[i] ≤ 105. root[0]n’est jamais-1, donc l’arbre comporte au moins un nœud.- L’array peut se terminer par des entrées
-1supplémentaires après le dernier nœud. - Les deux enfants d’un emplacement vide sont également vides, et la profondeur est d’au plus
14. - La règle d’ordre s’applique à chaque nœud, donc aucune valeur n’apparaît deux fois.
1 ≤ k ≤le nombre de nœuds dans l’arbre.
Exemples
- Entrée
- root = [41, 17, 65, 6, 29, -1, 90, -1, -1, 22]k = 4
- Sortie
- 29
- Explication
- Par ordre croissant, les valeurs sont
6, 17, 22, 29, 41, 65, 90, et la quatrième est29. C’est la plus grande des quatre valeurs du sous-arbre gauche de la racine.
- Entrée
- root = [12, 5, -1, 2, 9, -1, -1, -1, -1, 7, -1, -1, -1, -1, -1]k = 1
- Sortie
- 2
- Explication
- La plus petite valeur termine le chemin qui continue vers la gauche :
12,5,2. Le7sous9et le remplissage avec-1ne changent rien à cela.
Pour aller plus loin
Si l’arbre change souvent et qu’on vous demande de nombreuses fois la k-ième plus petite valeur, que pourrait stocker chaque nœud pour que chaque requête prenne O(h) ?
Indices
Ouvrez-les un par un. Chacun en dévoile un peu plus.
Quel parcours d’un arbre binaire de recherche énumère ses valeurs de la plus petite à la plus grande ?
Parcourir le sous-arbre gauche, puis le nœud, puis le sous-arbre droit donne les valeurs dans l’ordre trié. La
k-ième valeur produite par ce parcours est la réponse : tu peux donc t’arrêter là.Utilisez une pile. À partir du nœud actuel, empilez les nœuds tout en vous déplaçant vers l’enfant gauche. Dépilez le sommet et comptez-le ; arrêtez-vous au
ke dépilement. Sinon, déplacez-vous vers l’enfant droit du nœud dépilé à2*i+2et recommencez.
Solution
Un parcours infixe (sous-arbre gauche, nœud, sous-arbre droit) lit les valeurs d’un arbre binaire de recherche dans l’ordre croissant ; la k-ième valeur atteinte est donc la réponse. Effectue le parcours avec ta propre pile et arrête-toi à cette valeur ; aucun tri n’est nécessaire.
Collecter chaque valeur et trier
Intuition
Ignorez la structure : conservez chaque élément différent de -1, triez-les et renvoyez l’élément à la position k-1. Pour le premier exemple, la liste triée est 6, 17, 22, 29, 41, 65, 90, et la position 3 contient 29.
C’est correct pour n’importe quel arbre, ordonné ou non. C’est aussi son coût : cette méthode ignore l’ordre déjà présent dans l’arbre et nécessite O(n log n) pour le tri et O(n) de mémoire pour la copie.
Algorithme
- Récupère chaque entrée de
rootqui n’est pas-1. - Trie les valeurs récupérées par ordre croissant.
- Renvoie la valeur à la position
k-1.
def kthSmallest(root, k):
values = [v for v in root if v != -1] # every node, in any order
values.sort()
return values[k - 1]Parcours infixe dans une liste
Intuition
Sous chaque nœud, le sous-arbre gauche ne contient que des valeurs plus petites et le sous-arbre droit, uniquement des valeurs plus grandes. Parcourez le sous-arbre gauche, puis le nœud, puis le sous-arbre droit, et faites de même dans chaque sous-arbre : chaque nœud apparaît après toutes les valeurs plus petites et avant toutes les valeurs plus grandes, le résultat est donc trié. Dans le premier exemple, le parcours donne 6, 17, 22, 29, 41, 65, 90.
Un seul parcours remplace le tri : un temps de O(n) et un espace de O(n) pour la liste. Il parcourt tout l’arbre, même lorsque k = 1, alors que la réponse se trouve au bout du chemin le plus à gauche.
Algorithme
- Écrivez
inorder(i): renvoyez si l’emplacement est vide (au-delà de la fin ou-1). - Sinon, appelez
inorder(2*i+1), ajoutezroot[i]à la liste, puis appelezinorder(2*i+2). - Appelez
inorder(0). - Renvoyez l’élément de la liste à la position
k-1.
def kthSmallest(root, k):
n = len(root)
values = []
def inorder(i):
if i >= n or root[i] == -1:
return
inorder(2 * i + 1) # smaller values first
values.append(root[i])
inorder(2 * i + 2) # then larger ones
inorder(0)
return values[k - 1] # values is sortedParcours infixe itératif qui s’arrête à k
Intuition
Une pile explicite vous permet d’interrompre le parcours en cours de route. Allez aussi loin que possible vers la gauche, en empilant chaque nœud. Le nœud au sommet est la plus petite valeur qui n’a pas encore été comptabilisée, car toutes les valeurs plus petites se trouvent dans son sous-arbre gauche, qui est vide ou dont les valeurs ont déjà été comptabilisées. Dépilez-le et comptabilisez-le ; son sous-arbre droit vient ensuite dans l’ordre trié.
Pour k = 4 dans le premier exemple : empilez 41, 17, 6. Dépilez 6, puis 17, et passez à son enfant droit : empilez 29 et 22. Dépilez 22, puis 29, le quatrième. Le parcours ne touche jamais 65 ni 90.
La pile contient au maximum un nœud par niveau, donc l’espace utilisé est O(h). Le parcours descend une fois, puis dépile k fois : temps O(h + k).
Algorithme
- Commence avec une pile vide et
i = 0. - Tant que
iest un nœud réel, empile-le et passe à2*i+1. - Dépile l’élément au sommet dans
iet soustrais1àk. - Si
kvaut maintenant0, renvoieroot[i]. - Sinon, passe à
2*i+2et reviens à l’étape 2.
def kthSmallest(root, k):
n = len(root)
stack = [] # nodes whose left side is being visited, deepest on top
i = 0
while True:
while i < n and root[i] != -1: # go as far left as you can
stack.append(i)
i = 2 * i + 1
i = stack.pop() # the smallest value not counted yet
k -= 1
if k == 0:
return root[i]
i = 2 * i + 2 # then everything in its right subtree
Pièges et cas limites
- Lire le tableau dans l’ordre des index. L’ordre par niveau n’est pas trié : le premier exemple commence par
41, 17, 65. - Erreur de décalage de un pour
k. Le comptage commence à1: renvoyer la positionk-1dans la liste et arrêter le parcours lorsque le compte atteintk. - Ignorer le sous-arbre droit après un dépilement. Dans le deuxième exemple,
9et7se trouvent dans le sous-arbre droit de5, et le parcours ne les compterait jamais. - Considérer un enfant manquant comme réel. Un enfant est vide lorsque son index dépasse la fin ou contient
-1:22se trouve à l’index9, donc ses enfants19et20dépassent la fin. - Les tableaux Lua et R commencent à 1. Garder les index des nœuds à partir de 0 pour
2*i+1et lireroot[i + 1].
Questions fréquentes3
Quelle est la complexité temporelle de la recherche du k-ième plus petit élément dans un BST ?
Le parcours infixe itératif prend un temps de O(h + k) et utilise un espace supplémentaire de O(h) pour un arbre de profondeur h. Dans le pire des cas, lorsque k = n ou que l’arbre a la forme d’un chemin, il s’agit de O(n).
Comment trouver le kᵉ plus grand élément dans un BST ?
Inversez le parcours : le sous-arbre droit, puis le nœud, puis le sous-arbre gauche. Cela liste les valeurs par ordre décroissant. Allez aussi loin que possible vers la droite en empilant, dépilez et comptez, puis passez au fils gauche après chaque dépilement. Le k-ième dépilement est le k-ième plus grand.
Comment arrêter un parcours récursif en ordre à la k-ième valeur ?
Gardez un compteur en dehors de la récursion, initialisé à k. Soustrayez 1 après le retour du sous-arbre gauche d’un nœud, et enregistrez la valeur du nœud lorsque le compteur atteint 0. Après chaque appel, retournez immédiatement si la réponse est enregistrée. La récursion a alors les mêmes complexités que la version avec pile : O(h + k) en temps, O(h) en espace.
Problèmes similaires
Des problèmes qui reposent sur les mêmes idées. En résoudre deux ou trois, c’est ce qui ancre un schéma.
def kthSmallest(root, k):
# Écrivez le code iciTest #1
Test #2
Arguments
root = [41, 17, 65, 6, 29, -1, 90, -1, -1, 22] k = 4
Résultat attendu
29