દ્વિસંખ્યા શોધ વૃક્ષ એક દ્વિસંખ્યા વૃક્ષ છે જે ક્રમમાં અટલ રાખે છે : દરેક નોડ માટે, તેના ડાબા પેટમાંના બધા ચાવીઓ નાની હોય છે, અને તેના જમણા પેટમાંના બધા ચાવીઓ મોટી હોય છે. આ તમને દરેક પગલે સમસ્યાને અડધી કરીને શોધ કરવા દે છે.
8
/ \
3 10
/ \ \
1 6 14 left < node < right at every node
def search(node, key):
while node:
if key == node.val: return node
node = node.left if key < node.val else node.right # go one way
return None
def insert(node, key):
if node is None: return Node(key)
if key < node.val: node.left = insert(node.left, key)
else: node.right = insert(node.right, key)
return node
| પ્રક્રિયા | સંતુલિત | સૌથી વધુ (હતું) |
|---|---|---|
| search | O(log n) | O(n) |
| insert | O(log n) | O(n) |
| delete | O(log n) | O(n) |
સૌથી વધુ કેસ ત્યારે થાય છે જ્યારે ચાવીઓ સંકલિત ક્રમમાં ઉમેરવામાં આવે છે — વૃક્ષ ઊંચાઈ n ની શૃંખલা સૂચીમાં હતું બને છે.
BST તમને ક્રમિત, ગતિશીલ ડેટા આપે છે લોગરીધમિક પ્રક્રિયાઓ સાથે — ડેટાબેસ ઇન્ડેક્સ અને ક્રમિત નકશાઓનો વૈચારિક પૂર્વજ.
જીણું સમસ્યા સ્વ-સંતુલન વૃક્ષ ને પ્રેરણા આપે છે, साक્ષાત્કાર માં મુખ્ય અનુવર્તી વિષય.
વિગતવાર જવાબો સાથે IT ઇન્ટરવ્યૂ પ્રશ્નોની લાઇબ્રેરી — જુનિયરથી સિનિયર સુધી.
દાન કરો