writing new data structure

I have in my homework some question about data structure:

I have elements which consist of two fields

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

I need to write data structure with the following 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 开发者_如何学PythonI need is also O(logn)`

complexity for the memory is O(n)

can somebody please help, how can I create function Highest with current complexity? thanks in advance for any help.

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

edited

thank You for all of you guys, I can't get one small thing, how to store data:

            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?

You can use the AVL tree to find the element x and find the largest value in its left subtree and right subtree. So just walk down right until you can't and that will be the largest element in the subtree. Do that for the left and right branch and it should run in O(logn)

EDITED: So in response to your edited question, going off of how you're interpreting the question, wouldn't it make more sense to just find the largest element in the tree in general? If the node x that you call method on is not the highest, then the highest to the right will just be the largest element in the tree. Finding the largest takes O(log n) time.

Higest(x) with log(n) gives answer about AVL trees