Uma mediana de um AVL. Como tirar proveito do AVL?

Aqui está a fonte da minha pergunta.

Dada uma árvore de auto balanceamento (AVL), codifique um método que retorne a mediana.

(Mediana: o valor numérico que separa a metade superior de uma amostra de dados da metade inferior. Exemplo: se a série for

2, 7, 4, 9, 1, 5, 8, 3, 6

então a mediana é 5.)

Posso oferecer a seguinte solução:

1. Atravesse a árvore especificada e retorne o número de elementos.
2. Atravesse n / 2 + 1(se nfor ímpar) a árvore novamente aplicando uma caminhada em árvore em ordem. O valor do n / 2 + 1elemento th é a mediana.

Mas posso fazer isso com uma árvore de pesquisa binária, não posso? Existe um algoritmo melhor para um AVL?

Se você modificar a árvore AVL armazenando o tamanho da subárvore em cada nó, e não apenas na altura, poderá encontrar a mediana no tempo $O(\log n)$usando o fato de que a árvore está equilibrada. Para isso, escreva um procedimento mais geral. Selecione qual aceita um nó.$v$ e um número $k$e encontra o $k$o menor nó da subárvore com raiz em $v$.

Suponha que a subárvore esquerda (se houver) tenha $L$nós. E se$k \leq L$então recursamos para a subárvore esquerda. E se$k = L+1$ então voltamos $v$. Caso contrário, recuaremos para a subárvore direita, reduzindo$k$ de $L+1$.

O tempo de execução desse algoritmo é linear na altura da árvore, que é $O(\log n)$.

AVL é uma árvore de pesquisa binária com alguma propriedade especial: é uma árvore de auto-equilíbrio. Sua altura é sempre logarítmica. A árvore binária comum em um dos piores cenários pode ser uma lista vinculada (se você adicionar dados classificados) para que a altura seja n. A árvore AVL no pior cenário é a árvore de fibonacci.