पाठ 10 / 42

Binary Search Tree

Binary tree जहाँ left < node < right, क्रमबद्ध O(log n) search देता है।

क्रम अपरिवर्तनीय

हर node के लिए, उसके left subtree की सभी keys छोटी और right की सभी बड़ी। तो search binary search जैसा है: तुलना करें, फिर left या right जाएँ, हर चरण में tree आधा — O(h)।

Search और insert

दोनों root से एक पथ का अनुसरण करते हैं; insert नई key वहाँ रखता है जहाँ search असफल होता।

def search(node, key):
    while node and node.val != key:
        node = node.left if key < node.val else node.right
    return node

def insert(node, key):
    if not node: return Node(key)
    if key < node.val: node.left = insert(node.left, key)
    else:              node.right = insert(node.right, key)
    return node

In-order = क्रमबद्ध

BST का in-order traversal keys को आरोही क्रम में देता है। यह BST सत्यापित करने या k-वाँ सबसे छोटा तत्व खोजने का तेज़ तरीका है।

त्वरित जाँच: खाली असंतुलित BST में 1,2,3,4,5 क्रम में डालें। Search लागत हो जाती है...

  • O(log n)
  • O(n)
  • O(1)
Answer

O(n) — क्रमबद्ध insert दाईं ओर झुकी श्रृंखला बनाते हैं — असल में linked list। संतुलित trees (AVL, red-black) इसे ठीक करते हैं।