Skip to content

Commit abf8c3a

Browse files
laurentlucelaurentluce
committed
Revert delete mistake.
1 parent 3edbb25 commit abf8c3a

File tree

4 files changed

+515
-0
lines changed

4 files changed

+515
-0
lines changed

‎algorithms/binary_tree.py

+166
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,166 @@
1+
from __future__ import print_function
2+
3+
4+
class Node(object):
5+
"""Tree node: left and right child + data which can be any object
6+
7+
"""
8+
def __init__(self, data):
9+
"""Node constructor
10+
11+
@param data node data object
12+
"""
13+
self.left = None
14+
self.right = None
15+
self.data = data
16+
17+
def insert(self, data):
18+
"""Insert new node with data
19+
20+
@param data node data object to insert
21+
"""
22+
if self.data:
23+
if data < self.data:
24+
if self.left is None:
25+
self.left = Node(data)
26+
else:
27+
self.left.insert(data)
28+
elif data > self.data:
29+
if self.right is None:
30+
self.right = Node(data)
31+
else:
32+
self.right.insert(data)
33+
else:
34+
self.data = data
35+
36+
def lookup(self, data, parent=None):
37+
"""Lookup node containing data
38+
39+
@param data node data object to look up
40+
@param parent node's parent
41+
@returns node and node's parent if found or None, None
42+
"""
43+
if data < self.data:
44+
if self.left is None:
45+
return None, None
46+
return self.left.lookup(data, self)
47+
elif data > self.data:
48+
if self.right is None:
49+
return None, None
50+
return self.right.lookup(data, self)
51+
else:
52+
return self, parent
53+
54+
def delete(self, data):
55+
"""Delete node containing data
56+
57+
@param data node's content to delete
58+
"""
59+
# get node containing data
60+
node, parent = self.lookup(data)
61+
if node is not None:
62+
children_count = node.children_count()
63+
if children_count == 0:
64+
# if node has no children, just remove it
65+
if parent:
66+
if parent.left is node:
67+
parent.left = None
68+
else:
69+
parent.right = None
70+
else:
71+
self.data = None
72+
elif children_count == 1:
73+
# if node has 1 child
74+
# replace node by its child
75+
if node.left:
76+
n = node.left
77+
else:
78+
n = node.right
79+
if parent:
80+
if parent.left is node:
81+
parent.left = n
82+
else:
83+
parent.right = n
84+
else:
85+
self.left = n.left
86+
self.right = n.right
87+
self.data = n.data
88+
else:
89+
# if node has 2 children
90+
# find its successor
91+
parent = node
92+
successor = node.right
93+
while successor.left:
94+
parent = successor
95+
successor = successor.left
96+
# replace node data by its successor data
97+
node.data = successor.data
98+
# fix successor's parent node child
99+
if parent.left == successor:
100+
parent.left = successor.right
101+
else:
102+
parent.right = successor.right
103+
104+
def compare_trees(self, node):
105+
"""Compare 2 trees
106+
107+
@param node tree to compare
108+
@returns True if the tree passed is identical to this tree
109+
"""
110+
if node is None:
111+
return False
112+
if self.data != node.data:
113+
return False
114+
res = True
115+
if self.left is None:
116+
if node.left:
117+
return False
118+
else:
119+
res = self.left.compare_trees(node.left)
120+
if res is False:
121+
return False
122+
if self.right is None:
123+
if node.right:
124+
return False
125+
else:
126+
res = self.right.compare_trees(node.right)
127+
return res
128+
129+
def print_tree(self):
130+
"""Print tree content inorder
131+
132+
"""
133+
if self.left:
134+
self.left.print_tree()
135+
print(self.data, end=" ")
136+
if self.right:
137+
self.right.print_tree()
138+
139+
def tree_data(self):
140+
"""Generator to get the tree nodes data
141+
142+
"""
143+
# we use a stack to traverse the tree in a non-recursive way
144+
stack = []
145+
node = self
146+
while stack or node:
147+
if node:
148+
stack.append(node)
149+
node = node.left
150+
else:
151+
# we are returning so we pop the node and we yield it
152+
node = stack.pop()
153+
yield node.data
154+
node = node.right
155+
156+
def children_count(self):
157+
"""Return the number of children
158+
159+
@returns number of children: 0, 1, 2
160+
"""
161+
cnt = 0
162+
if self.left:
163+
cnt += 1
164+
if self.right:
165+
cnt += 1
166+
return cnt

‎algorithms/list.py

+122
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,122 @@
1+
def find_int(i, l):
2+
"""Find integer in a sorted list.
3+
4+
Example: 4 in [1, 3, 4, 6, 7, 9] -> 2
5+
@param i integer to find.
6+
@param l sorted list.
7+
@returns index if found, None if not.
8+
"""
9+
if l:
10+
p_idx = len(l) / 2
11+
p = l[p_idx]
12+
if i == p:
13+
return p_idx
14+
elif len(l) == 1:
15+
return
16+
elif i < p:
17+
res = find_int(i, l[:p_idx])
18+
if res:
19+
return res
20+
elif i > p:
21+
res = find_int(i, l[p_idx:])
22+
if res:
23+
return res + p_idx
24+
25+
26+
def find_max_sub(l):
27+
"""Find subset with higest sum.
28+
29+
Example: [-2, 3, -4, 5, 1, -5] -> (3,4), 6
30+
@param l list
31+
@returns subset bounds and highest sum
32+
"""
33+
# max sum
34+
max = l[0]
35+
# current sum
36+
m = 0
37+
# max sum subset bounds
38+
bounds = (0, 0)
39+
# current subset start
40+
s = 0
41+
for i in range(len(l)):
42+
m += l[i]
43+
if m > max:
44+
max = m
45+
bounds = (s, i)
46+
elif m < 0:
47+
m = 0
48+
s = i+1
49+
return bounds, max
50+
51+
52+
def merge_sort(l):
53+
"""Sort list using merge sort.
54+
55+
Complexity: O(n log n)
56+
57+
@param l list to sort.
58+
@returns sorted list.
59+
"""
60+
def merge(l1, l2):
61+
"""Merge sorted lists l1 and l2.
62+
63+
[1, 2, 4], [1, 3, 4, 5] -> [1, 1, 2, 3, 4, 5]
64+
@param l1 sorted list
65+
@param l2 sorted list
66+
@returns merge sorted list
67+
"""
68+
res = []
69+
i = 0
70+
j = 0
71+
while i < len(l1) and j < len(l2):
72+
if l1[i] <= l2[j]:
73+
res.append(l1[i])
74+
i += 1
75+
elif l2[j] < l1[i]:
76+
res.append(l2[j])
77+
j += 1
78+
79+
while i < len(l1):
80+
res.append(l1[i])
81+
i += 1
82+
83+
while j < len(l2):
84+
res.append(l2[j])
85+
j += 1
86+
87+
return res
88+
89+
length = len(l)
90+
if length <= 1:
91+
return l
92+
mid = length / 2
93+
h1 = merge_sort(l[:mid])
94+
h2 = merge_sort(l[mid:])
95+
96+
return merge(h1, h2)
97+
98+
99+
def quicksort(l):
100+
"""Sort list using quick sort.
101+
102+
Complexity: O(n log n). Worst: O(n2)
103+
104+
@param l list to sort.
105+
@returns sorted list.
106+
"""
107+
if len(l) <= 1:
108+
return l
109+
110+
pivot = l[0]
111+
less = []
112+
equal = []
113+
greater = []
114+
for e in l:
115+
if e < pivot:
116+
less.append(e)
117+
elif e == pivot:
118+
equal.append(e)
119+
else:
120+
greater.append(e)
121+
122+
return quicksort(less) + equal + quicksort(greater)

0 commit comments

Comments
 (0)