A Crit-bit Tree is a binary search tree used for storing strings, especially strings of arbitrary length, in a compressed form.
The Crit-bit refers to the bit position in the common prefix of two strings where they differ. The tree is a form of binary trie with a compressed path.
The tree is used to efficiently handle string searches and updates, with each node storing a single bit representing the largest common prefix bit difference between the two strings.
Steps:
Insertion: When inserting, the tree finds the position where the strings differ and creates a new node at the “crit-bit” position.
Search: Searching in a Crit-bit Tree works by following the path based on the crit-bit values (common prefix bit position) and comparing the strings.
Time Complexity:
Insertion: O(k), where k is the length of the string.
Search: O(k), where k is the length of the string.
class CritBitTreeNode: def __init__(self, key=None): self.key = key self.left = None self.right = None self.bit_pos = None # Position of the critical bitclass CritBitTree: def __init__(self): self.root = None def insert(self, key): self.root = self._insert(self.root, key) def _insert(self, node, key): if not node: return CritBitTreeNode(key) # Find the critical bit where they differ common_prefix_length = self._common_prefix_length(node.key, key) if common_prefix_length < len(node.key): node.bit_pos = common_prefix_length if key[node.bit_pos] == '0': node.left = self._insert(node.left, key) else: node.right = self._insert(node.right, key) return node def _common_prefix_length(self, key1, key2): length = 0 while length < len(key1) and length < len(key2) and key1[length] == key2[length]: length += 1 return length# Example usagetree = CritBitTree()tree.insert("hello")tree.insert("helium")tree.insert("hero")