class Node(object):
def __init__(self, character):
self.character = character
self.leftNode = None
self.middleNode = None
self.rightNode = None
self.value = 0
class TST(object):
def __init__(self):
self.rootNode = None
def put(self, key, value):
self.rootNode = self.putItem(self.rootNode, key, value, 0)
def putItem(self, node, key, value, index):
c = key[index]
if node is None:
node = Node(c)
if c < node.character:
node.leftNode = self.putItem(node.leftNode, key, value, index)
elif c > node.character:
node.rightNode = self.putItem(node.rightNode, key, value, index)
elif index < len(key) - 1:
node.middleNode = self.putItem(node.middleNode, key, value,
index + 1)
else:
node.value = value
return node;
def get(self, key):
node = self.getItem(self.rootNode, key, 0)
if node is None:
return -1
return node.value
def getItem(self, node, key, index):
if node is None:
return None
c = key[index]
if c < node.character:
return self.getItem(node.leftNode, key, index)
elif c > node.character:
return self.getItem(node.rightNode, key, index)
elif index < len(key) - 1:
return self.getItem(node.middleNode, key, index + 1)
else:
return node
if __name__ == "__main__":
tst = TST()
tst.put("apple", 100)
tst.put("orange", 200)
print(tst.get("orange"))
# Faster insertion and deletion than AVL, slower search
class Color:
RED = 1
BLACK = 2
class Node:
def __init__(self, data, parent=None, color=Color.RED):
self.data = data
self.color = color
self.parent = parent
self.left = None
self.right = None
class RedBlackTree:
def __init__(self):
self.root = None
def insert(self, data):
if not self.root:
self.root = Node(data)
self.violate(self.root)
else:
self.insert_node(data, self.root)
def insert_node(self, data, node):
if data < node.data:
if node.left:
self.insert_node(data, node.left)
else:
node.left = Node(data, node)
self.violate(node.left)
else:
if node.right:
self.insert_node(data, node.right)
else:
node.right = Node(data, node)
self.violate(node.right)
def violate(self, node):
parent_node = None
grand_parent_node = None
while node != self.root and node.parent.color == Color.RED:
parent_node = node.parent
grand_parent_node = parent_node.parent
if grand_parent_node is None:
return
if parent_node == grand_parent_node.left:
uncle = grand_parent_node.right
if uncle and uncle.color == Color.RED:
# case 1 and case 4
print("Re-coloring node %s to RED" % grand_parent_node.data)
grand_parent_node.color = Color.RED
print("Re-coloring node %s to BLACK" % parent_node.data)
parent_node.color = Color.BLACK
uncle.color = Color.BLACK
node = grand_parent_node
else:
# case 2: uncle node is black and node is a right child
if node == parent_node.right:
self.rotate_left(parent_node)
node = parent_node
parent_node = node.parent
# case 3
parent_node.color = Color.BLACK
grand_parent_node.color = Color.RED
print("Re-color %s to BLACK" % parent_node.data)
print("Re-color %s to RED" % grand_parent_node.data)
self.rotate_right(grand_parent_node)
else:
uncle = grand_parent_node.left
if uncle and uncle.color == Color.RED:
# case 1 and case 4
print("Re-coloring node %s to RED" % grand_parent_node.data)
grand_parent_node.color = Color.RED
print("Re-coloring node %s to BLACK" % parent_node.data)
parent_node.color = Color.BLACK
uncle.color = Color.BLACK
node = grand_parent_node
else:
# case 2: uncle node is black and node is a right child
if node == parent_node.left:
self.rotate_right(parent_node)
node = parent_node
parent_node = node.parent
# case 3
parent_node.color = Color.BLACK
grand_parent_node.color = Color.RED
print("Re-color %s to BLACK" % parent_node.data)
print("Re-color %s to RED" % grand_parent_node.data)
self.rotate_left(grand_parent_node)
if self.root.color == Color.RED:
print("Recoloring the root to black...")
self.root.color = Color.BLACK
def traverse(self):
if self.root is not None:
self.traverse_in_order(self.root)
def traverse_in_order(self, node):
if node.left:
self.traverse_in_order(node.left)
l = ''
r = ''
p = ''
if node.left is not None:
l = node.left.data
else:
l = 'NULL'
if node.right is not None:
r = node.right.data
else:
r = 'NULL'
if node.parent is not None:
p = node.parent.data
else:
p = 'NULL'
print("%s left: %s right: %s parent: %s color: %s" % (node.data, l, r, p, node.color))
if node.right:
self.traverse_in_order(node.right)
def rotate_right(self, node):
print("Rotating to the right on node ", node.data)
temp_left_node = node.left
t = temp_left_node.right
temp_left_node.right = node
node.left = t
if t is not None:
t.parent = node
temp_parent = node.parent
node.parent = temp_left_node
temp_left_node.parent = temp_parent
if temp_left_node.parent is not None and temp_left_node.parent.left == node:
temp_left_node.parent.left = temp_left_node
if temp_left_node.parent is not None and temp_left_node.parent.right == node:
temp_left_node.parent.right = temp_left_node
if node == self.root:
self.root = temp_left_node
def rotate_left(self, node):
print("Rotating to the left on node ", node.data)
temp_right_node = node.right
t = temp_right_node.left
temp_right_node.left = node
node.right = t
if t is not None:
t.parent = node
temp_parent = node.parent
node.parent = temp_right_node
temp_right_node.parent = temp_parent
if temp_right_node.parent is not None and temp_right_node.parent.left == node:
temp_right_node.parent.left = temp_right_node
if temp_right_node.parent is not None and temp_right_node.parent.right == node:
temp_right_node.parent.right = temp_right_node
if node == self.root:
self.root = temp_right_node
rbt = RedBlackTree()
rbt.insert(32)
rbt.insert(10)
rbt.insert(55)
rbt.insert(1)
rbt.insert(19)
rbt.insert(79)
rbt.insert(16)
rbt.insert(23)
rbt.insert(12)
rbt.traverse()
def tree_equal(node1, node2):
if not node1 and not node2:
return True
if not node1 or not node2:
return False
return node1.val == node2.val and \
tree_equal(node1.left, node2.left) and \
tree_equal(node1.right, node2.right)
function treeEqual(node1, node2) {
if (!node1 && !node2) {
return true;
}
if (!node1 || !node2) {
return false;
}
return node1.val == node2.val &&
treeEqual(node1.left, node2.left) &&
treeEqual(node1.right, node2.right);
}
def tree_mirror(node):
if not node:
return
node.left, node.right = node.right, node.left
tree_mirror(node.left)
tree_mirror(node.right)function treeMirror(node) {
if (!node) {
return;
}
let temp = node.left;
node.left = node.right;
node.right = temp;
treeMirror(node.left);
treeMirror(node.right);
}
# Various iterative ways of traversing a tree.
def inorder_traversal(root):
"""
:type root: TreeNode
:rtype: List[int]
"""
if not root:
return []
result = []
stack = [root]
while len(stack) > 0:
curr_node = stack.pop()
if curr_node.left:
stack.append(curr_node)
stack.append(curr_node.left)
curr_node.left = None
else:
result.append(curr_node.val)
if curr_node.right:
stack.append(curr_node.right)
return result
def preorder_traversal(root):
"""
:type root: TreeNode
:rtype: List[int]
"""
if not root:
return []
result = []
stack = [root]
while len(stack) > 0:
curr_node = stack.pop()
result.append(curr_node.val)
if curr_node.right:
stack.append(curr_node.right)
if curr_node.left:
stack.append(curr_node.left)
return result
def postorder_traversal(root):
"""
:type root: TreeNode
:rtype: List[int]
"""
if not root:
return []
result = []
stack = [root]
while len(stack) > 0:
curr_node = stack.pop()
if curr_node.left:
stack.append(curr_node)
stack.append(curr_node.left)
curr_node.left = None
elif curr_node.right:
stack.append(curr_node)
stack.append(curr_node.right)
curr_node.right = None
else:
result.append(curr_node.val)
return result
# Various iterative ways of traversing a tree.
def inorder_traversal(root):
"""
:type root: TreeNode
:rtype: List[int]
"""
if not root:
return []
result = []
stack = [root]
while len(stack) > 0:
curr_node = stack.pop()
if curr_node.left:
stack.append(curr_node)
stack.append(curr_node.left)
curr_node.left = None
else:
result.append(curr_node.val)
if curr_node.right:
stack.append(curr_node.right)
return result
def preorder_traversal(root):
"""
:type root: TreeNode
:rtype: List[int]
"""
if not root:
return []
result = []
stack = [root]
while len(stack) > 0:
curr_node = stack.pop()
result.append(curr_node.val)
if curr_node.right:
stack.append(curr_node.right)
if curr_node.left:
stack.append(curr_node.left)
return result
def postorder_traversal(root):
"""
:type root: TreeNode
:rtype: List[int]
"""
if not root:
return []
result = []
stack = [root]
while len(stack) > 0:
curr_node = stack.pop()
if curr_node.left:
stack.append(curr_node)
stack.append(curr_node.left)
curr_node.left = None
elif curr_node.right:
stack.append(curr_node)
stack.append(curr_node.right)
curr_node.right = None
else:
result.append(curr_node.val)
return result