ਇੱਕ ਬਾਈਨਰੀ ਸਰਚ ਟ੍ਰੀ ਇੱਕ ਬਾਈਨਰੀ ਟ੍ਰੀ ਹੈ ਜਿਸ ਵਿਚ ਇੱਕ ਅਰਡਰਿੰਗ ਇਨਵੇਰੀਅੰਟ ਹੈ: ਹਰੇਕ ਨੋਡ ਲਈ, ਇਸ ਦੇ ਖੱਬੇ ਸਬਟ੍ਰੀ ਵਿਚ ਸਾਰੀਆਂ ਕੁੰਜੀਆਂ ਛੋਟੀਆਂ ਹੁੰਦੀਆਂ ਹਨ, ਅਤੇ ਇਸ ਦੇ ਸੱਜੇ ਸਬਟ੍ਰੀ ਵਿਚ ਸਾਰੀਆਂ ਕੁੰਜੀਆਂ ਵੱਡੀਆਂ ਹੁੰਦੀਆਂ ਹਨ। ਇਹ ਤੁਹਾਨੂੰ ਹਰੇਕ ਪੜਾਅ ਤੇ ਸਮੱਸਿਆ ਨੂੰ ਅੱਧਾ ਕਰਕੇ ਖੋਜ ਕਰਨ ਦਿੰਦਾ ਹੈ।
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
| Operation | Balanced | Worst (degenerate) |
|---|---|---|
| search | O(log n) | O(n) |
| insert | O(log n) | O(n) |
| delete | O(log n) | O(n) |
ਸਭ ਤੋਂ ਖੋਆ ਕੇਸ ਉਦੋਂ ਹੁੰਦਾ ਹੈ ਜਦੋਂ ਕੁੰਜੀਆਂ ਕ੍ਰਮਬੱਧ ਕ੍ਰਮ ਵਿਚ ਸ਼ਾਮਲ ਕੀਤੀਆਂ ਜਾਂਦੀਆਂ ਹਨ — ਟ੍ਰੀ n ਉਚਾਈ ਦੀ ਇੱਕ ਲਿੰਕਡ ਲਿਸਟ ਵਿਚ ਖਰਾਬ ਹੋ ਜਾਂਦੀ ਹੈ।
BST ਤੁਹਾਨੂੰ ਕ੍ਰਮਬੱਧ, ਗਤੀਸ਼ੀਲ ਡੇਟਾ ਲੋਗਰਿਥਮਿਕ ਓਪਰੇਸ਼ਨਾਂ ਦੇ ਨਾਲ ਦਿੰਦਾ ਹੈ — ਡਾਟਾਬੇਸ ਇੰਡੈਕਸ ਅਤੇ ਕ੍ਰਮਬੱਧ ਨਕਸ਼ੀ ਦਾ ਸੰਕਲਪਨਾਤਮਕ ਪੂਰਵਜ।
डिजेनेरेशन ਸਮੱਸਿਆ self-balancing trees ਨੂੰ ਪ੍ਰेਰਿਤ ਕਰਦੀ ਹੈ, ਸਾਖਤਕਾਰਾਂ ਵਿਚ ਇੱਕ ਮੁੱਖ ਅਨੁਵਰਤੀ ਵਿਸ਼ਾ।