- Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathconstruct.py
More file actions
Latest commit
146 lines (123 loc) · 4.3 KB
/
Copy pathconstruct.py
File metadata and controls
146 lines (123 loc) · 4.3 KB
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
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
from __future__ importannotations
fromcollectionsimportdeque
fromdataclassesimportdataclass
fromitertoolsimportcount
fromrandomimportseed, shuffle
fromtimeitimporttimeit
fromtypingimportAny, Optional
fromtraversalimportdepth_first_inorder, depth_first_preorder
@dataclass
classNode:
value: Any
left: Optional[Node] =None
right: Optional[Node] =None
classTree:
def__init__(self, *values):
self.root=None
forvalueinvalues:
self.insert(value)
def__eq__(self, other):
ifnotisinstance(other, Tree):
returnFalse
returnself.root==other.root
definsert(self, value):
ifself.rootisNone:
self.root=Node(value)
returnself.root
node=self.root
whileTrue:
ifvalue==node.value:
raiseValueError(f"duplicate value {value}")
elifvalue<node.value:
ifnode.leftisnotNone:
node=node.left
continue
node.left=new=Node(value)
else:
ifnode.rightisnotNone:
node=node.right
continue
node.right=new=Node(value)
returnnew
defconstruct_from_preorder(values):
ivalues=iter(values)
root=node=Node(next(ivalues))
stack=deque([root])
forvalueinivalues:
ifvalue<node.value:
node.left=node=Node(value)
stack.appendleft(node)
else:
whilestackandvalue>stack[0].value:
node=stack.popleft()
node.right=node=Node(value)
stack.appendleft(node)
returnroot
defconstruct_from_preorder_inorder(pre_order, in_order):
# print(f"\nStack recreating tree from PO {pre_order} and IO {in_order}")
pre_iter=iter(pre_order)
root=node=Node(next(pre_iter))
stack=deque([node])
right=False
forivalueinin_order:
# print(f"\nProcessing in-order value {ivalue}, stack: {stack}")
ifstackandivalue==stack[0].value:
node=stack.popleft()
right=True
# print(f"- on top of in stack, going up tp {node}!")
continue
forpvalueinpre_iter:
ifright:
# print(f"- appending {pvalue} to right of {node}")
node.right=node=Node(pvalue)
else:
# print(f"- appending {pvalue} to left of {node}")
node.left=node=Node(pvalue)
ifright:=pvalue==ivalue:
break
stack.appendleft(node)
returnroot
defpreorder_permutation_generator(preorder):
"""Generates different structural permutations for a single preorder sequence."""
root, *additional=map(Node, preorder)
def_constructor(root, nodes):
ifnotnodes:
yieldroot
return
cursor=root
whileTrue:
whilecursor.rightisnotNone:
cursor=cursor.right
cursor.right=nodes[0]
yieldfrom_constructor(root, nodes[1:])
cursor.right=None
ifcursor.leftisNone:
cursor.left=nodes[0]
yieldfrom_constructor(root, nodes[1:])
cursor.left=None
return
cursor=cursor.left
return_constructor(root, additional)
defmain():
seed(1)
dfsio=depth_first_inorder
dfspo=depth_first_preorder
numbers=list(range(128))
forattemptincount(1):
shuffle(numbers)
tree=Tree(*numbers)
foralgoin [construct_from_preorder]:
retree=algo(dfspo(tree))
asserttree.root==retree
treetime=timeit(lambda: algo(dfspo(tree)), number=5000)
print(algo.__name__, treetime)
foralgoin [construct_from_preorder_inorder]:
retree=algo(dfspo(tree), dfsio(tree))
asserttree.root==retree
treetime=timeit(lambda: algo(dfspo(tree), dfsio(tree)), number=5000)
print(algo.__name__, treetime)
print("")
ifattempt%1000==0:
print(f"{attempt} reconstructions without failure")
if__name__=="__main__":
main()