Escribir una nueva estructura de datos: estructuras de datos, teoría de la complejidad.

Tengo en mi tarea alguna pregunta sobre la estructura de los datos:

Tengo elementos que constan de dos campos.

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

Necesito escribir la estructura de datos con la siguiente interfaz:

**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)

¿Alguien puede ayudar? ¿Cómo puedo crear una función? Highest con current complexity? Gracias de antemano por cualquier ayuda.

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

editado

Gracias por todos ustedes, no puedo conseguir una pequeña cosa, cómo almacenar datos:

            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?

Respuestas

Puedes usar el árbol AVL para encontrar el elemento xy encuentre el valor más grande en su subárbol izquierdo y subárbol derecho. Así que simplemente camine hacia la derecha hasta que pueda "t" y ese será el elemento más grande en el subárbol. Haga eso para la rama izquierda y derecha y debería ejecutarse en O (logn)

EDITADO: Entonces, respondiendo a su pregunta editada, ¿cómo tendría más sentido encontrar el elemento más grande en el árbol en general? Si el nodo x al que llama método no es el más alto, entonces el más alto a la derecha será el elemento más grande del árbol. Encontrar el mayor tiempo toma O (log n).

Higest (x) con log (n) da respuesta sobre árboles AVL