tira/viikko12/treeheight.py

import random
import time


class Node:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None


class TreeSet:
    def __init__(self):
        self.root = None
        self.max_depth = -1

    def add(self, value):
        max_depth = 0

        if not self.root:
            self.root = Node(value)
            self.max_depth += 1
            return

        node = self.root
        while True:
            if node.value == value:
                break
            max_depth += 1
            if node.value > value:
                if not node.left:
                    node.left = Node(value)
                    break
                node = node.left
            else:
                if not node.right:
                    node.right = Node(value)
                    break
                node = node.right

        self.max_depth = max(self.max_depth, max_depth)

    def height(self):
        return self.max_depth


if __name__ == "__main__":
    start = time.time()
    numbers_smallest = TreeSet()
    for i in range(1000):
        numbers_smallest.add(i)
    result_smallest = numbers_smallest.height()
    end_smallest = time.time()

    numbers_biggest = TreeSet()
    for i in sorted([i for i in range(1000)], key=lambda x: random.random()):
        numbers_biggest.add(i)
    result_biggest = numbers_biggest.height()
    end_biggest = time.time()

    print(
        f"Total: {end_biggest - start:.2f}, smallest: {end_smallest - start:.2f}, biggest: {end_biggest - end_smallest:.2f}"
    )
    print("Height smallest:", result_smallest, "Height biggest", result_biggest)