Skip to content
Snippets Groups Projects
Select Git revision
  • d2c41f1574d95f497d5e2cd719d14d0b0b58bd57
  • master default protected
2 results

kgrams_test.py

Blame
  • tree_successor.py 1.25 KiB
    #!/usr/bin/env python3
    
    class Node:
        """Node in a binary tree `Tree`"""
    
        def __init__(self, key, left=None, right=None, parent=None):
            self.key = key
            self.left = left
            self.right = right
            self.parent = parent
    
    class Tree:
        """A simple binary search tree"""
    
        def __init__(self, root=None):
            self.root = root
    
        def insert(self, key):
            """Insert key into the tree.
    
            If the key is already present, do nothing.
            """
            if self.root is None:
                self.root = Node(key)
                return
    
            node = self.root
            while node.key != key:
                if key < node.key:
                    if node.left is None:
                        node.left = Node(key, parent=node)
                    node = node.left
                else:
                    if node.right is None:
                        node.right = Node(key, parent=node)
                    node = node.right
    
        def successor(self, node=None):
            """Return successor of the given node.
    
            The successor of a node is the node with the next greater key.
            Return None if there is no such node.
            If the argument is None, return the node with the smallest key.
            """
            # TODO: Implement
            raise NotImplementedError