-
Notifications
You must be signed in to change notification settings - Fork 0
/
bst.py
122 lines (101 loc) · 3.32 KB
/
bst.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
119
120
121
122
from __future__ import annotations
from dataclasses import dataclass
from typing import Optional, List, SupportsInt, TypeAlias, Union, SupportsFloat
T: TypeAlias = Union[int, float]
def from_list(_: List[T], i: int = 0) -> Optional[Node]:
if len(_) == 0:
return None
value = _[i]
if value is None:
return None
li = 2 * i + 1
ri = 2 * i + 2
left = None
if len(_) > li:
left = from_list(_, li)
right = None
if len(_) > ri:
right = from_list(_, ri)
return Node(_[i], left, right)
def _validate(node: Optional[Node], minimum: float = float('-inf'), maximum: float = float('inf')) -> bool:
if node is None:
return True
return minimum < node.value < maximum\
and _validate(node.left, minimum, node.value)\
and _validate(node.right, node.value, maximum)
@dataclass
class Node:
value: T
left: Optional[Node] = None
right: Optional[Node] = None
def validate(self) -> bool:
return _validate(self)
def maximum(self) -> T:
node = self
while True:
if node.right is None:
return node.value
node = node.right
def minimum(self) -> T:
node = self
while True:
if node.left is None:
return node.value
node = node.left
def contains(self, value: T) -> bool:
node = self
while True:
if node is None:
return False
elif node.value == value:
return True
elif value < node.value:
node = node.left
elif value > node.value:
node = node.right
def insert(self, value: T) -> Node:
node = self
while True:
if node.value == value:
return node
elif value < node.value:
if node.left is None:
node.left = Node(value)
return node.left
elif node.left.value < value:
tmp = Node(value, left=node.left)
node.left = tmp
return tmp
else:
node = node.left
elif value > node.value:
if node.right is None:
node.right = Node(value)
return node.right
elif node.right.value > value:
tmp = Node(value, right=node.right)
node.right = tmp
return tmp
else:
node = node.right
def delete(self, value: T) -> bool:
node = self
while True:
if node.value == value:
raise RuntimeError("Cannot delete root.")
elif value < node.value:
if node.left is None:
return False
elif node.left.value == value:
node.left = node.left.left
return True
else:
node = node.left
elif value > node.value:
if node.right is None:
return False
elif node.right.value == value:
node.right = node.right.right
return True
else:
node = node.right