Code Monkey home page Code Monkey logo

binary-search-tree's Introduction

Binary Search Tree

Implementation of a BST using Functional Programming

You can use this implementaion online using repl.it here: Binary Search Tree

Table of Contents

  1. Introduction
  2. List of Functions
  3. Examples
  4. Description of Functions
  5. How to Use

Introduction

This implementation of a binary search tree (BST) follows the Functional Programming Paradigm as it adheres to:

  • Immutability
  • Pure functions
  • Avoiding side-effects

It also allows for any data which can be ordered using a total order to be stored (not only numbers). This is done using a strict total order.

Functions

The following functions are implemented:

  • BST(strict_total_order)
  • insert(tree, element)
  • remove(tree, element)
  • contains(tree, element)
  • size(tree)
  • is_empty(tree)
  • get_min(tree)
  • get_max(tree)
  • dump(tree) **this is an impure function

Examples

Real Numbers Sorted on <

Create a BST with elements 1 - 10 sorted by the strict total order "<"

from random import shuffle
from functools import reduce

# create the list of elements to insert
elements_to_insert = [num for num in range(1, 11)]
shuffle(elements_to_insert) # ensures the tree is probabaly near minimal height

# create the BST
strict_total_order = lambda x, y : x < y
empty_bst = BST(strict_total_order)
my_bst = reduce(insert, elements_to_insert, empty_bst)

# print the contents of the BST
dump(my_bst)

without_2 = remove(my_bst, 2)
dump(without_2)

print(is_empty(my_bst))

print(size(my_bst))

print(get_min(my_bst))

The output is:

1 2 3 4 5 6 7 8 9 10
1 3 4 5 6 7 8 9 10
False
10
1

Objects

Using a BST to organize dogs. Dogs are sorted by their age first, and if their age is the same, they are sorted by name alphabetically.

from functools import reduce

# Dog class
class Dog:
	def __init__(self, name, age):
		self.name = name
		self.age = age

dog1 = Dog("Brownie", 1)
dog2 = Dog("Jack", 8)
dog3 = Dog("Spark", 4)
dog4 = Dog("Ruby", 4)
dogs = [dog1, dog2, dog3, dog4]

# order by "<" on age first, then alphabetically on name
def strict_total_order(dog1, dog2):
	age1 = dog1.age
	age2 = dog2.age
	name1 = dog1.name.lower()
	name2 = dog2.name.lower()
	if age1 != age2:
		return age1 < age2
	elif name1 != name2:
		return sorted([name1, name2])[0] == name1
	else: #names and age are equal
		return False

empty_bst = BST(strict_total_order)

dogs_bst = reduce(insert, dogs, empty_bst)

print(contains(dogs_bst, dog1))
print(contains(dogs_bst, Dog("Bear", 2)))
print(get_min(dogs_bst).name)
print(size(dogs_bst))

The output is:

True
False
Brownie
4

Description of Functions

BST(strict_total_order)

  • O(1) time
  • takes a strict total order
  • returns an empty BST with that total order

insert(tree, element)

  • O(h) time where h is the height of tree
  • takes a BST and an element
  • returns a BST with the elements of tree and element

remove(tree, element)

  • O(h) time where h is the height of tree
  • takes a non-empty BST which contains element
  • returns a BST with the elements of tree except for element

contains(tree, element)

  • O(h) time where h is the height of tree
  • takes a BST and an element
  • returns true if element is in tree; false otherwise

size(tree)

  • O(n) time where n = size(tree)
  • takes a BST
  • returns the number of elements in tree

is_empty(tree)

  • O(1) time
  • takes a BST
  • returns true if tree is an empty BST; false otherwise

get_min(tree)

  • O(h) time where h is the height of tree
  • takes a non-empty BST
  • returns the minimum element of tree

get_max(tree)

  • O(h) time where h is the height of tree
  • takes a non-empty BST
  • returns the maximum element of tree

dump(tree)

  • this is an impure function
  • O(n) time where n = size(tree)
  • takes a BST
  • prints the elements of tree

How to Use

  1. Follow this link to the online editor: Binary Search Tree.

  2. Replace the example in main.py with your program. You may need to create an account to modify the code.

  3. Run the program by clicking the green Run button.

binary-search-tree's People

Contributors

tansonlee avatar

Watchers

 avatar

Recommend Projects

  • React photo React

    A declarative, efficient, and flexible JavaScript library for building user interfaces.

  • Vue.js photo Vue.js

    ๐Ÿ–– Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.

  • Typescript photo Typescript

    TypeScript is a superset of JavaScript that compiles to clean JavaScript output.

  • TensorFlow photo TensorFlow

    An Open Source Machine Learning Framework for Everyone

  • Django photo Django

    The Web framework for perfectionists with deadlines.

  • D3 photo D3

    Bring data to life with SVG, Canvas and HTML. ๐Ÿ“Š๐Ÿ“ˆ๐ŸŽ‰

Recommend Topics

  • javascript

    JavaScript (JS) is a lightweight interpreted programming language with first-class functions.

  • web

    Some thing interesting about web. New door for the world.

  • server

    A server is a program made to process requests and deliver data to clients.

  • Machine learning

    Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.

  • Game

    Some thing interesting about game, make everyone happy.

Recommend Org

  • Facebook photo Facebook

    We are working to build community through open source technology. NB: members must have two-factor auth.

  • Microsoft photo Microsoft

    Open source projects and samples from Microsoft.

  • Google photo Google

    Google โค๏ธ Open Source for everyone.

  • D3 photo D3

    Data-Driven Documents codes.