-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathbinary_tree.py
119 lines (99 loc) · 4.24 KB
/
binary_tree.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
from logging import NullHandler
from turtle import right
class BinaryTreeNode:
def __init__(self, data, parent = None, left = None, right = None):
self.data = data
self.parent = parent
self.left = left
self.right = right
# We divide the tree using the rule that larger values go to the right
# and lesser values go to the left
class BinarySearchTree:
def __init__(self):
self.root = None
# Preserve the structure of the binary search tree where larger values
# are placed on the right and lesser values are placed on the left
def insert(self, data):
if self.root is None:
self.root = BinaryTreeNode(data)
return self.root
else:
inserted_node = BinaryTreeNode(data)
parent_node = None
current_node = self.root
while current_node is not None:
parent_node = current_node
# No need to insert if the node is already in the tree
if data == current_node.data:
return current_node
elif data < current_node.data:
current_node = current_node.left
else:
current_node = current_node.right
inserted_node.parent = parent_node
if data < parent_node.data:
parent_node.left = inserted_node
else:
parent_node.right = inserted_node
return inserted_node
# Keep going right until we run out of nodes
def tree_max(self, start_node: BinaryTreeNode):
current_node = start_node
while current_node.right is not None:
current_node = current_node.right
return current_node
# Keep going left until we run out of nodes
def tree_min(self, start_node: BinaryTreeNode):
current_node = start_node
while current_node.left is not None:
current_node = current_node.left
return current_node
# Transfer old linkages to new linkages
def shift(self, old_node: BinaryTreeNode, new_node: BinaryTreeNode):
if old_node.parent is None:
self.root = new_node
elif old_node.data == old_node.parent.left.data:
old_node.parent.left = new_node
else:
old_node.parent.right = new_node
if new_node is not None:
new_node.parent = old_node.parent
def successor(self, start_node: BinaryTreeNode):
if start_node.right is not None:
return self.tree_min(start_node.right)
current_node = start_node
parent_node = start_node.parent
while parent_node is not None and parent_node.right is not None and current_node.data == parent_node.right.data:
current_node = parent_node
parent_node = parent_node.parent
return parent_node
# The simplest deletion happens when we are on a leaf node or alsmost at
# at a leaf node. Things get more complicated when we delete an item from
# the middle of the tree
def delete(self, start_node: BinaryTreeNode, data):
target_node = self.find(start_node, data)
if target_node is None:
return
if target_node.left is None:
self.shift(target_node, target_node.right)
elif target_node.right is None:
self.shift(target_node, target_node.left)
else:
node = self.successor(target_node)
if node.parent.data != data:
self.shift(node, node.right)
node.right = target_node.right
node.right.parent = node
self.shift(target_node, node)
node.left = target_node.left
node.left.parent = node
# We can divide and conquer through the tree because of the
# properties enforced by insert and delete.
def find(self, start_node: BinaryTreeNode, data):
current_node = start_node
while current_node is not None and current_node.data != data:
if data < current_node.data:
current_node = current_node.left
else:
current_node = current_node.right
return current_node