இரும்பாகத் தேடல் மரம் என்பது வரிசை மாறாதடன் கொண்ட ஒரு இரும்பாக மரமாகும்: ஒவ்வொரு முனைக்கும், அதன் இடக் கீழ்மரத்தில் உள்ள அனைத்து விசைகளும் சிறியது, மற்றும் அதன் வலக் கீழ்மரத்தில் உள்ள அனைத்து விசைகளும் பெரியது. இது ஒவ்வொரு படிநிலையிலும் சிக்கலைப் பாதியாகக் குறைத்து தேடலை செய்ய உங்களுக்கு அனுமதிக்கிறது.
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
| செயல்பாடு | சமன்சست்தம் | மிக மோசமான சூழ்நிலை (சிதைந்த) |
|---|---|---|
| தேடல் | O(log n) | O(n) |
| செருகல் | O(log n) | O(n) |
| நீக்கம் | O(log n) | O(n) |
மிக மோசமான சூழ்நிலை விசைகளை வரிசைப்படுத்தப்பட்ட வரிசையில் செருகும் போது ஏற்படுகிறது — மரம் உயரம் n கொண்ட ஒரு இணைக்கப்பட்ட பட்டியலாக சிதைந்து விடுகிறது.
BST கள் உங்களுக்கு வரிசைப்படுத்தப்பட்ட, இயங்குவிலக்ஷணிய தரவு மற்றும் மடக்கை செயல்பாடுகளை தருகின்றன — தரவுத்தளக் குறியீடுகள் மற்றும் ஆணையிடப்பட்ட வரைபடங்களின் கோட்பாட்டுப் முன்னோடி.
சிதைவின் சிக்கல் தன்-சமன்சச்யமான மரங்கள் ஐ ஊக்குவிக்கிறது, இது சேர்க்கையிலூக்கு ஒரு முக்கிய பிற்படுத்தல் விஷயம்.