mirror of
https://github.com/iritmaximus/tira.git
synced 2026-10-12 19:13:47 +03:00
115 lines
2.6 KiB
Python
115 lines
2.6 KiB
Python
import math
|
|
class Node:
|
|
def __init__(self, value):
|
|
self.value = value
|
|
self.left = None
|
|
self.right = None
|
|
|
|
def __repr__(self):
|
|
return f"({self.value}, l: {self.left}, r: {self.right})"
|
|
|
|
|
|
class TreeSet:
|
|
def __init__(self):
|
|
self.root = None
|
|
|
|
def add(self, value):
|
|
if not self.root:
|
|
self.root = Node(value)
|
|
return
|
|
|
|
node = self.root
|
|
while True:
|
|
if node.value == value:
|
|
return
|
|
if node.value > value:
|
|
if not node.left:
|
|
node.left = Node(value)
|
|
return
|
|
node = node.left
|
|
else:
|
|
if not node.right:
|
|
node.right = Node(value)
|
|
return
|
|
node = node.right
|
|
|
|
def prev(self, value):
|
|
node = self.root
|
|
|
|
if node is None:
|
|
return None
|
|
|
|
highest_lowest = 0
|
|
while node:
|
|
print(value, node, highest_lowest)
|
|
if node.value < value:
|
|
highest_lowest = max(node.value, highest_lowest)
|
|
node = node.right
|
|
|
|
elif value <= node.value:
|
|
node = node.left
|
|
|
|
else:
|
|
break
|
|
|
|
print("prev:", highest_lowest)
|
|
print()
|
|
if highest_lowest == 0:
|
|
return None
|
|
return highest_lowest
|
|
|
|
def next(self, value):
|
|
node = self.root
|
|
|
|
if node is None:
|
|
return None
|
|
|
|
lowest_highest = math.inf
|
|
while node:
|
|
print(value, node, lowest_highest)
|
|
if value < node.value:
|
|
lowest_highest = min(node.value, lowest_highest)
|
|
node = node.left
|
|
|
|
elif node.value <= value:
|
|
node = node.right
|
|
|
|
else:
|
|
break
|
|
|
|
print("next:", lowest_highest)
|
|
print()
|
|
if lowest_highest == math.inf:
|
|
return None
|
|
return lowest_highest
|
|
|
|
|
|
if __name__ == "__main__":
|
|
numbers = TreeSet()
|
|
|
|
numbers.add(3)
|
|
numbers.add(2)
|
|
numbers.add(5)
|
|
numbers.add(7)
|
|
|
|
assert numbers.prev(5) == 3
|
|
assert numbers.prev(4) == 3
|
|
assert numbers.prev(3) == 2
|
|
assert numbers.prev(2) == None
|
|
|
|
assert numbers.next(4) == 5
|
|
assert numbers.next(5) == 7
|
|
assert numbers.next(6) == 7
|
|
assert numbers.next(7) == None
|
|
|
|
numbers = TreeSet()
|
|
numbers.add(1)
|
|
assert numbers.prev(2) == 1
|
|
assert numbers.next(2) == None
|
|
numbers.add(2)
|
|
assert numbers.prev(2) == 1
|
|
assert numbers.next(2) == None
|
|
numbers.add(2)
|
|
assert numbers.prev(3) == 2
|
|
assert numbers.next(1) == 2
|