написание новой структуры данных

Question

У меня в домашней задаче есть вопрос о структуре данных:

У меня есть элементы, которые состоят из двух полей

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

Мне нужно написать структуру данных со следующим интерфейсом:

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

Может кто-нибудь помочь, как я могу создать функцию Highest с current complexity? заранее спасибо за любую помощь.

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

изм

спасибо вам всем, ребята, я не могу получить одну маленькую вещь, как хранить данные:

            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?

Answer 1

Вы можете использовать дерево AVL, чтобы найти элемент x и найти наибольшее значение в его левом поддереве и правом поддереве. Так что просто идите вниз, пока не сможете, и это будет самый большой элемент в поддереве. Сделайте это для левой и правой ветви, и он должен работать в O (logn)

Редакция: Итак, в ответ на ваш отредактированный вопрос, исходя из того, как вы интерпретируете вопрос, не имеет ли больше смысла просто найти самый большой элемент в дереве в целом? Если узел x, на котором вы вызываете метод, не является самым высоким, то самый высокий справа будет просто самым большим элементом в дереве. Нахождение наибольшего занимает O (log n) времени.

Answer 2

Наивысший (x) с log (n) дает ответ о деревьях AVL