escrevendo nova estrutura de dados - estruturas de dados, teoria da complexidade

Tenho na minha lição de casa algumas perguntas sobre a estrutura de dados:

Eu tenho elementos que consistem em dois campos

class Element{
int point;       // point on the ax
int height;
};

Preciso escrever a estrutura de dados com a seguinte interface:

**Init(N)** - any complexity You want, initialization of N elements
**Update(x,y)** - if element on the point x exists, change its height to the y, complexity O(logn)
**Highest(x)** - find the highest element on the left from the element x and on the right of the element, `complexity I need is also O(logn)`

complexity for the memory is O(n)

alguém pode ajudar, como posso criar função Highest com current complexity? Agradecemos antecipadamente por qualquer ajuda.

P.S I can use hash tables and also AVL trees

editado

obrigado por todos vocês, não consigo entender uma pequena coisa, como armazenar dados:

            10,1
|               |
5,14           17,23
|         |      |        |
2,5       7,25  5,10    20,100

this is my tree all keys are the points on the ax X, number after comma is the height;
if I want for example to find the highest on the right from NODE (2,5), I need to pass
all nodes till the (20,100), cause this one is highest, am I wrong?

Respostas:

Você pode usar a árvore AVL para encontrar o elemento xe encontre o maior valor em sua subárvore esquerda e subárvore direita. Então, desça para a direita até que você possa "t e esse será o maior elemento na subárvore. Faça isso para o ramo esquerdo e direito e ele deve ser executado em O (logn)

EDITADO:Então, em resposta à sua pergunta editada, falando sobre como você está interpretando a pergunta, não faria mais sentido apenas encontrar o maior elemento na árvore em geral? Se o nó x no qual você chama o método não for o mais alto, o mais alto à direita será apenas o maior elemento da árvore. Encontrar o maior leva tempo O (log n).

Maior (x) com log (n) dá resposta sobre árvores AVL