బైనరీ సెర్చ్ ట్రీ అనేది ఆర్డరింగ్ ఇన్వేరియంట్ ఉన్న ఒక బైనరీ ట్రీ: ప్రతి నోడ్ కోసం, దాని ఎడమ సబ్ట్రీలో ఉన్న అన్ని కీలు చిన్నవి, మరియు దాని కుడి సబ్ట్రీలో ఉన్న అన్ని కీలు పెద్దవి. ఇది ప్రతి దశలో సమస్యను సగానికి తగ్గించడం ద్వారా శోధించడానికి మిమ్మల్ని అనుమతిస్తుంది.
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 లు మీకు సార్ట్ చేసిన, డైనమిక్ డేటా మరియు లాగరిథమిక్ ఆపరేషన్లను ఇస్తాయి — డేటాబేస్ ఇండెక్సులు మరియు ఆర్డర్ చేసిన మ్యాప్ల యొక్క సంభావిత పూర్వీకుడు.
అధోకృష్టం సమస్య స్వయం-సమతుల్యమైన చెట్లును ప్రేరేపిస్తుంది, ఇంటర్వ్యూలలో ఒక ప్రధాన అనుసరణ విషయం.