A collection of implementations of common algorithms
You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.

47 lines
1.0 KiB

#! /usr/bin/env python3
from random import randint
from pprint import PrettyPrinter
# Construct a binary search tree
# Also create a function to search it
pp = PrettyPrinter(indent=4)
class Branch:
def __init__(self, left, value, right):
self.value = value
self.left = left
self.right = right
def __repr__(self):
return "(%s) %s (%s)" % (repr(self.left), self.value, repr(self.right))
def split(xs):
l = int(len(xs) / 2)
return (xs[0:l], xs[l], xs[l+1:])
def bst(xs):
if not xs:
return None
left, middle, right = split(xs)
return Branch(bst(left), middle, bst(right))
def makeBST(xs):
return bst(sorted(xs))
def findBST(tree, x):
if tree is None:
return None
if tree.value == x:
return tree
if x < tree.value:
return findBST(tree.left, x)
return findBST(tree.right, x)
test = [randint(1,50) for _ in range(20)]
print("finding %s" % test[4])
print(findBST(makeBST(test), test[4]))