Created
July 1, 2013 13:30
-
-
Save landau/5900769 to your computer and use it in GitHub Desktop.
Successor Binary Tree
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
class Node(object): | |
def __init__(self, val): | |
self.val = val | |
self.left = None | |
self.right = None | |
self.parent = None | |
def has_no_kids(self): | |
return self.right is None and self.left is None | |
def has_right(self): | |
return not self.right is None | |
def has_left(self): | |
return not self.left is None | |
def has_kids(self): | |
return not self.has_no_kids() | |
def is_right(self): | |
return self.parent.right == self | |
def is_left(self): | |
return self.parent.left == self | |
def __lt__(self, val): | |
return self.val < val | |
def __gt__(self, val): | |
return self.val > val | |
def __eq__(self, val): | |
return self.val == val | |
def __str__(self): | |
return "[Node val: %d]" % self.val | |
class Tree(object): | |
def __init__(self): | |
self.root = None | |
def put(self, val): | |
self.root = self._put(self.root, val, None) | |
def _put(self, node, val, parent): | |
if node is None: | |
node = Node(val) | |
if isinstance(parent, Node): | |
node.parent = parent | |
if val < node: | |
node.left = self._put(node.left, val, node) | |
elif val > node: | |
node.right = self._put(node.right, val, node) | |
else: | |
node.val = val | |
return node | |
def get(self, val): | |
return self._get(self.root, val) | |
def _get(self, node, val): | |
while not node is None: | |
if val < node: node = node.left | |
elif val > node: node = node.right | |
else: return node | |
return None | |
def successor(self, val): | |
node = self.get(val) | |
# Can only have a succesor if has right | |
if node == self.root: | |
if node.has_right(): | |
return self.sink_left(node.right).val | |
else: | |
return None | |
# is left node | |
elif node.is_left(): | |
if node.has_no_kids() or node.has_left(): return node.parent.val | |
# Go right and then left till None | |
if node.has_right(): | |
return self.sink_left(node.right).val | |
# is right node | |
elif node.is_right(): | |
parent = node.parent | |
# No right successor possible from self | |
# This means we swim up the tree until a left node is found | |
# That left nodes parent is the succesor of this right node | |
if not node.has_right(): | |
# parent's parent does not exist aka parent is root | |
# no successor | |
if parent.parent is None: | |
return None | |
else: | |
# parent is a right node | |
# continue up the tree til we have a left node | |
node = self.swim_till_left(node) | |
if node is None: | |
return None | |
return node.parent.val | |
# Has a right child | |
else: | |
return self.sink_left(node.right).val | |
# iterate down and left until | |
# no left is found | |
def sink_left(self, node): | |
while not node.left is None: | |
node = node.left | |
return node | |
# iterate up until node is not a right node | |
# once the left node is found, return it | |
def swim_till_left(self, node): | |
while True: | |
parent = node.parent | |
# No left node found | |
if parent is None or parent.parent is None: return None | |
# parent is still a right node | |
# continue up the tree | |
if parent.is_right(): | |
node = parent | |
else: | |
return parent | |
if __name__ == "__main__": | |
from sys import stdout | |
vals = [30, 25, 20, 26, 14, 28, 8, 15, 27, 29, 52, 49, 63] | |
tree = Tree() | |
[tree.put(val) for val in vals] | |
for val in vals: | |
stdout.write("Successor to %d: " % val) | |
print tree.successor(val) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment