દ્વિસંખ્યા શોધ વૃક્ષ એક દ્વિસંખ્યા વૃક્ષ છે જે ક્રમમાં અટલ રાખે છે : દરેક નોડ માટે, તેના ડાબા પેટમાંના બધા ચાવીઓ નાની હોય છે, અને તેના જમણા પેટમાંના બધા ચાવીઓ મોટી હોય છે. આ તમને દરેક પગલે સમસ્યાને અડધી કરીને શોધ કરવા દે છે.
અટલ
text
8
/ \
3 10
/ \ \
1 6 14 left < node < right at every node
શોધ અને ઉમેરણ
python
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 ની શૃંખલা સૂચીમાં હતું બને છે.
સમજૌતા
- શક્તિઓ : O(n) માં ક્રમિત પસાર કરણ ; શ્રેણી પ્રશ્નો અને અનુગામી/પુર્વેસરને સમર્થન આપે છે.
- નબળાઈ : પોતે કોઈ સંતુલન ગ્યારંટી નથી — O(log n) માં રહેવા માટે AVL અથવા લાલ-કાળો વિવિધતા જરૂરી છે.
તે શા માટે મહત્વપૂર્ણ છે
BST તમને ક્રમિત, ગતિશીલ ડેટા આપે છે લોગરીધમિક પ્રક્રિયાઓ સાથે — ડેટાબેસ ઇન્ડેક્સ અને ક્રમિત નકશાઓનો વૈચારિક પૂર્વજ.
જીણું સમસ્યા સ્વ-સંતુલન વૃક્ષ ને પ્રેરણા આપે છે, साक્ષાત્કાર માં મુખ્ય અનુવર્તી વિષય.