प्राप्त करें वर्तमान में मैं अपने विश्वविद्यालय प्रोजेक्ट के लिए जावा में बीएसटी लागू कर रहा हूं। जैसा कि हम जानते हैं, बीएसटी एक एकल इकाई खोजने में काफी अच्छा है जो एक संतुलित पेड़ में ओ (लॉग एन) है।द्विआधारी खोज पेड़ के अंतराल के रूप में तेजी से क्रमबद्ध सरणी
लेकिन मूल्य a और b के बीच खोज कैसे करें? (एक < ख)
चलो कहते हैं कि मैं इस पेड़
│ ┌── 125
│ ┌── 122
│ │ └── 120
│ ┌── 117
│ │ │ ┌── 113
│ │ └── 112
│ │ └── 108
│ ┌── 86
│ │ │ ┌── 85
│ │ └── 72
└── 59
│ ┌── 56
│ ┌── 52
│ ┌── 47
│ │ │ ┌── 43
│ │ └── 39
│ │ │ ┌── 38
│ │ └── 36
└── 28
│ ┌── 18
│ ┌── 15
└── 2
└── 1
मैं एक विधि range(a,b)a और b समावेशी के बीच मान देने के लिए बनाना चाहते हैं करते हैं। (नोट: a और b पेड़ में आवश्यक नहीं कर रहे हैं!)
उदाहरण के लिए: range(53,112) वापस आ जाएगी 56,59,72,85,86,108,112
यहाँ मेरी छद्म कोड
/* recursive method */
range(a,b)
range(a,b,root);
/* helper method */
range(a,b,node)
if (a <= node.value <= b)
if (node.left != null) and (node.value != a)
range(a,b,node.left)
print node.value
if (node.right != null) and (node.value != b)
range(a,b,node.right)
else if node.value < a
if (node.right != null)
range(a,b,node.right)
else // node.value > b
if (node.left != null)
range(a,b,node.left)
है लेकिन मुझे लगता है मेरी विधि धीमी है।
उदाहरण के लिए, एक क्रमबद्ध सरणी में, हमें a और b पर बाइनरी खोज करना होगा और उनका संबंधित अनुक्रमणिका प्राप्त करना होगा। इसके बाद, हम a की अनुक्रमणिका से b की अनुक्रमणिका में पुन: प्रयास करते हैं।
क्या यह सच है कि बीएसटी कई मूल्यों को खोजने पर धीमा प्रदर्शन करेगा? क्या मेरे एल्गोरिदम को एक क्रमबद्ध सरणी के रूप में तेज़ी से सुधारना संभव है?