नई डेटा संरचना लिखना - डेटा संरचनाएं, जटिलता-सिद्धांत

मेरे पास मेरे होमवर्क में डेटा संरचना के बारे में कुछ सवाल हैं:

मेरे पास ऐसे तत्व हैं जिनमें दो फ़ील्ड शामिल हैं

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?

उत्तर:

आप तत्व एक्स को खोजने के लिए एवीएल पेड़ का उपयोग कर सकते हैंऔर इसके बाएं सबट्री और राइट सबट्री में सबसे बड़ा मूल्य पाते हैं। इसलिए जब तक आप "t" नहीं कर सकते, तब तक दाईं ओर चलें और यह सबट्री में सबसे बड़ा तत्व होगा। बाईं और दाईं शाखा के लिए इसे करें और इसे O (logn) में चलाना चाहिए।

संपादित: तो आपके संपादित प्रश्न के जवाब में, आप कैसे इस प्रश्न की व्याख्या कर रहे हैं, क्या यह सामान्य रूप से पेड़ में सबसे बड़ा तत्व खोजने के लिए अधिक समझ में नहीं आता है? यदि आप जिस नोड x को विधि कहते हैं वह उच्चतम नहीं है, तो सही से उच्चतम पेड़ में सबसे बड़ा तत्व होगा। सबसे बड़ा ओ (लॉग एन) समय लगता है।

Higest (x) log (n) के साथ AVL पेड़ों के बारे में जवाब देता है