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

bst = None
file = open(file_name, 'r')
line_number = 0

while True:
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

stock_file = './data/stock.csv'

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

bst = None
file = open(file_name, 'r', encoding="utf-8")
line_number = 0

while True:
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'
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)}")```