Nodes in a binary search tree that span a range
-
05-11-2019 - |
Pergunta
I have a binary search tree of height $h$ with an integer in each leaf. I also have a range $[\ell,u]$. I want to find a set of nodes that span the range $[\ell,u]$, i.e., a set $S$ of nodes such that the leaves under $S$ form all (and only) those leaves containing integers in the range $[\ell,u]$. How large does $S$ need to be, in the worst case, as a function of the height $h$? How do I find such a set explicitly?
Nenhuma solução correta
Licenciado em: CC-BY-SA com atribuição
Não afiliado a cs.stackexchange