Contents
Binary Search Trees
A binary search tree, also called an ordered or sorted binary tree, is a rooted binary tree data structure with the key of each internal node being greater than all the keys in the respective node’s left subtree and less than the ones in its right subtree
Visit the following resources to learn more:
- articleHow to Implement Binary Search Tree in Python
- articleBinary Search Tree in Python
- videoTree Data Structure | Illustrated Data Structures
| Characteristic | Description |
|---|---|
| Definition | A Binary Search Tree (BST) is a binary tree where each node has at most two children, and the left child contains values less than the parent node, while the right child contains values greater than the parent node. |
| Properties | - In-order Traversal yields values in ascending order.<br> - Search Time is O(log n) on average if the tree is balanced.<br> - Insertion and Deletion can be O(log n) on average. |
| Balancing | BSTs can become unbalanced, leading to O(n) time complexity for operations. Balanced versions like AVL trees and Red-Black trees maintain O(log n) complexity. |
| Operations | - Search: Find a value.<br> - Insert: Add a new value.<br> - Delete: Remove a value.<br> - Traversal: Visit nodes in a specific order (in-order, pre-order, post-order). |
| Memory Usage | Uses additional memory for storing pointers (left and right children) in each node. |
| Applications | Used in various applications including searching, sorting, and maintaining sorted data. |
| Python Libraries | Python’s standard library does not include a direct implementation of BSTs, but you can use custom implementations or third-party libraries. |
Examples of Binary Search Tree Implementations in Python
| Library | Example Usage |
|---|---|
| Custom Implementation | BSTs can be implemented from scratch by defining a Node class and a BinarySearchTree class. <br> Example: <br> python <br> class Node:<br> def __init__(self, key):<br> self.left = None<br> self.right = None<br> self.value = key<br> <br> class BinarySearchTree:<br> def __init__(self):<br> self.root = None<br> def insert(self, key):<br> if self.root is None:<br> self.root = Node(key)<br> else:<br> self._insert(self.root, key)<br> def _insert(self, node, key):<br> if key < node.value:<br> if node.left is None:<br> node.left = Node(key)<br> else:<br> self._insert(node.left, key)<br> else:<br> if node.right is None:<br> node.right = Node(key)<br> else:<br> self._insert(node.right, key)<br> |
bintrees | A third-party library that provides balanced binary search trees. <br> Example: <br> python <br> from bintrees import RBTree <br> tree = RBTree() <br> tree.insert(1, 'value1') <br> tree.insert(2, 'value2') <br> print(tree[1]) # Outputs 'value1' <br> |
sortedcontainers | A third-party library that provides SortedList, SortedDict, and SortedSet, which use balanced trees internally. <br> Example: <br> python <br> from sortedcontainers import SortedDict <br> d = SortedDict() <br> d[1] = 'value1' <br> d[2] = 'value2' <br> print(d[1]) # Outputs 'value1' <br> |