Lekcja – Binary Search Tree – właściwości
from time import time, sleep
class Node:
def __init__(self, id, data):
self.id = id
self.data = data
self.left = None
self.right = None
self.depth = None
def __repr__(self):
return f"<{self.id}/{self.depth}>"
def insert(parent, child, depth=0):
if parent is None:
child.depth = depth
return child
elif parent.id == child.id:
return parent
elif child.id < parent.id:
parent.left = insert(parent.left, child, parent.depth+1)
else:
parent.right = insert(parent.right, child, parent.depth+1)
return parent
def load_stock_file(file_name):
bst = None
file = open(file_name, 'r')
line = file.readline()
line_number = 0
while True:
line = file.readline()
if not line:
break
data = line.split(',')
line_number +=1
#print(line_number, data[0], '/', data[1])
node = Node(data[0], data[1])
bst = insert(bst, node)
file.close()
return bst
# https://www.nasdaq.com/market-activity/stocks/screener?exchange=NASDAQ&render=download
stock_file = './data/stock.csv'
bst = load_stock_file(stock_file)
print('Done')
def max_depth(node):
if node is None:
return 0
else:
left_depth = max_depth(node.left) + 1
right_depth = max_depth(node.right) + 1
return max(left_depth, right_depth)
print(f"Max depth: {max_depth(bst)}")
print(f"Balance info: nodes on left: {max_depth(bst.left)} nodes on right: {max_depth(bst.right)}")
def count(node, delay=0):
sleep(delay)
if node is None:
return 0
else:
left_count = count(node.left, delay)
right_count = count(node.right, delay)
return left_count + right_count + 1
print(f"Count: {count(bst)}")
print(f"Balance info: nodes on left: {count(bst.left)} nodes on right: {count(bst.right)}")
start_time = time()
count(bst.left, 0.001)
print(f"Operation on left {time() - start_time} s")
start_time = time()
count(bst.right, 0.001)
print(f"Operation on right {time() - start_time} s")
Lab
class City:
def __init__(self, id, country, population):
self.id = id
self.country = country
self.population = population
self.left = None
self.right = None
self.depth = None
def __repr__(self):
return f"<{self.id}/{self.depth}>"
def insert(parent, child, depth=0):
if parent is None:
child.depth = depth
return child
elif parent.id == child.id:
return parent
elif child.id < parent.id:
parent.left = insert(parent.left, child, parent.depth+1)
else:
parent.right = insert(parent.right, child, parent.depth+1)
return parent
def load_file(file_name):
bst = None
file = open(file_name, 'r', encoding="utf-8")
line = file.readline()
line_number = 0
while True:
line = file.readline()
if not line:
break
data = line.split(',')
line_number +=1
city_ascii = data[1].strip().replace('"','').replace("'",'').replace("`",'').upper()
country = data[4].replace('"','').replace("'",'').replace("`",'').upper()
try:
population = int(data[9].replace('"',''))
except ValueError:
population = -1
node = City(city_ascii, country, population)
bst = insert(bst, node)
file.close()
return bst
# https://www.kaggle.com/juanmah/world-cities
stock_file = './data/worldcities.csv'
bst = load_file(stock_file)
print('Done')
def max_depth(node):
if node is None:
return 0
else:
left_depth = max_depth(node.left) + 1
right_depth = max_depth(node.right) + 1
return max(left_depth, right_depth)
def count(node):
if node is None:
return 0
else:
left_count = count(node.left)
right_count = count(node.right)
return left_count + right_count + 1
def sum_population(node):
if node is None:
return 0
else:
p = 0 if node.population < 0 else node.population
left_count = sum_population(node.left)
right_count = sum_population(node.right)
return left_count + right_count + p
print(f"Max depth: {max_depth(bst)}")
print(f"Balance info: nodes on left: {max_depth(bst.left)} nodes on right: {max_depth(bst.right)}")
print(f"Count: {count(bst)}")
print(f"Balance info: nodes on left: {count(bst.left)} nodes on right: {count(bst.right)}")
print(f"Population: {sum_population(bst)}")