from time import time from sys import argv class BinaryNode: """ A node with payload and two children. We use it to simplify splitting algorithm. """ def __init__ (self, key, left = None, right = None): """ Create an binary node """ self.key = key self.left = left self.right = right def __repr__(self): return "[{}]".format (self.key) class Node: """ A node from 2-3 tree. It could contain 1 or 2 keys. Let x designate the first Element, and let y correspond to the second one (possibly non-existent). The x should always be less than y. A node may have up to 3 children. Some children could be empty. They equal to None. The left subtree contains nodes whose keys are less than x. The keys of middle subtree are between x and y. The right subtree contains only keys greater than y. Always x < y (comparing keys) _____ |x|y| +-+-+ / | \ / | \ / | \ / | \ ----- ------- ----- |. 0: node = stack.pop() if node.x is not None : yield node.x if node.y is not None : yield node.y if node.left is not None : stack.append (node.left) if node.middle is not None : stack.append (node.middle) if node.right is not None : stack.append (node.right) def is_leaf (self): """ Really important """ return self.middle == None and self.left == None and self.right == None def add (self, a): """ Add BinaryNode 'a' to the current node ensuring key's order x < y and moving pointers to children comme il faut. Return False if there is no place (see split). """ if self.y is not None: return False left = a.left right = a.right if self.x is None: # very first case, when the root is empty self.left, self.x, self.middle = left, a.key, right ## if a < self.x ## ## BEFORE ==================> AFTER ## ## self self ## __________ ____________ ## |x| None | | a | x | ## +-+------+ +---+------+ ## / | \ / | \ ## | M None left right M ## ^ ## | Wherefrom Binary Node comes ## | a < x ## --- ## | a | ## --- ## / \ ## left right ## ## The figures of the same kind are useful ## to better understand the code of add(...) ans split(...) ## Feel free to draw it yourself ! if a.key < self.x: self.x, self.y = a.key, self.x self.left, self.middle, self.right = left, right, self.middle if a.key > self.x: self.y = a.key self.middle, self.right = left, right return True def split (self, splitter): """ Split current node using a given binary_node, returns a new binary_node. Return False if we should not split the node. """ if self.y is None: return False x, y = self.x, self.y if splitter.key < x : el = self.x left = Node (splitter.key) left.left, left.middle = splitter.left, splitter.right right = Node (self.y) right.left, right.middle = self.middle, self.right elif splitter.key > y : el = self.y left = Node (self.x) left.left, left.middle = self.left, self.middle right = Node (splitter.key) right.left, right.middle = splitter.left, splitter.right else: el = splitter.key left = Node (self.x) left.left, left.middle = self.left, splitter.left right = Node (self.y) right.left, right.middle = splitter.right, self.right return BinaryNode (el, left, right) def add_split_repeat (self, bnode, path_to_leaf): """ Add BinaryNode element to the last node of the path_to_leaf, spliting and pushing up to the root when needed. Nodes from path_to_leaf should correspond to the path from the root to the leaf. Return the (possibly new) root. """ root = path_to_leaf[0] while len (path_to_leaf) > 0: node = path_to_leaf.pop() added = node.add (bnode) if added: return root if not added: bnode = node.split (bnode) if len (path_to_leaf) == 0: new_root = Node(bnode.key) new_root.left = bnode.left new_root.middle = bnode.right return new_root def __repr__ (self): """ For debug purposes """ return "[ left = {}, x = {}, middle = {}, y = {}, right = {}] ".format( self.left, self.x, self.middle, self.y, self.right ) class arbre: """ Simple Arbre B (variante 2-3) store """ def __init__(self): """ Creates a 2-3 B-tree """ self.root = Node() def contains (self, key): """ Return true if Find a corresponding list of values or return None if key does not exists in Arbalet. WARNING! It returns a pointer to the list actually stored in the tree. """ c = self.root while True: if c is None : return False if c.x is None : return False if key == c.x : return True if key < c.x : c = c.left; continue if c.y is None : c = c.middle; continue if key == c.y : return True if key < c.y : c = c.middle; continue c = c.right def insert (self, key): ### Key already exists, do nothing if self.contains (key) : return ### When key is a new new = BinaryNode (key) c = self.root ### Find a corresponding leaf, remembering the path path_to_leaf = [] while True: path_to_leaf.append (c) if c.is_leaf (): self.root = c.add_split_repeat (new, path_to_leaf) return else: if key < c.x : c = c.left; continue if c.y is None : c = c.middle; continue if key < c.y : c = c.middle; continue c = c.right def __repr__(self): """ For debug purposes """ return str(self.root) def test_arbalet(): print ('We test...') c = arbre() c.insert (1) c.insert (11) c.insert (21) assert c.contains(1211) == False c.insert (1211) assert c.contains(1211) == True assert c.contains(111) == False assert c.contains(1) == True c.insert (111221) c.insert (312211) assert c.contains(1) == True assert c.contains(1211) == True a = arbre() b = arbre() a.insert ("test") a.insert ("tost") a.insert ("hzhh") a.insert ("test") b.insert ("test2") assert a.contains('test') == True assert a.contains('test2') == False assert b.contains('test2') == True assert b.contains('test') == False print ('Tests are OK!') if __name__ == "__main__": test_arbalet()