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"))
def tree_equal(node1, node2):
if not node1 and not node2:
return True
if not node1 or not node2:
function treeEqual(node1, node2) {
if (!node1 && !node2) {
return true;
}
if (!node1 || !node2) {
are another relation-based data structure, which specialize in representing hierarchical structures. Like a linked list, they’re populated with Node objects that contain a data value and one or more pointers to define its relation to immediate nodes.
Each tree has a root node that all other nodes branch off from. The root contains pointers to all elements directly below it, which are known as its child nodes. These child nodes can then have child nodes of their own. Binary trees cannot have nodes with more than two child nodes.
# 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()
The most common application of the binary tree is a binary search tree. Binary search trees excel at searching large collections of data, as the time complexity depends on the depth of the tree rather than the number of nodes.
Binary search trees have four strict rules:
The left subtree contains only nodes with elements lesser than the root.
The right subtree contains only nodes with elements greater than the root.
Left and right subtrees must also be a binary search tree. They must follow the above rules with the “root” of their tree.
There can be no duplicate nodes, i.e. no two nodes can have the same value.
# 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
def tree_mirror(node):
if not node:
return
node.left, node.right = node.right, node.left
tree_mirror(node.left)
function treeMirror(node) {
if (!node) {
return;
}
let temp = node.left;
node.left = node.right;
node.right