sbbst (Self Balancing Binary Search Tree)

A Python implementation of a self balancing binary search tree (AVL Tree). Useful to practice, study and see how a SBBST works.

Introduction

A self-balancing binary search tree is a data structure, a kind advanced one I would say, that optimizes the times for insertion, deletion and serching. Even though there a few types of SBBST (2-3 tree, AA tree, AVL tree, B tree, Red-black tree, ...), in this library I decided to implement the AVL Tree because I consider it as the easiest one.

It has O(N) space in memory and its respectives times and functions are:

Time complexity	Function in the class	Action
O(1)	sbbst.getSize()	Size of the tree
O(1)	sbbst.getHeightTree()	Height of the tree
O(logN)	sbbst.search(x)	Search value
O(logN)	sbbst.insert(x)	Insert value
O(logN)	sbbst.delete(x)	Delete value
O(logN)	sbbst.getMinVal()	Minimum value
O(logN)	sbbst.getMaxVal()	Maximum value
O(K+logN)	sbbst.kthsmallest(k)	Kth Minimum value
O(K+logN)	sbbst.kthlargest(k)	Kth Maximum value
O(N)	str(sbbst)	Visualize the tree

I made the library sbbst with the intention that you can use it easily for your own projects, learning or coding competitions (in which case I would suggest to compile your program with Pypy instead of Python3 and download the code directly from my Github and modify it as your necessities). I used this structure (with a few changes so it can work out with intervals instead of numbers) in the Facebook Hacker Cup 2020 and it was fast enough to pass the time complexity, though I would suggest to migrate to C++ (thing that I have not done properly yet [sept 2020]).

Requirements

• Python 2.7+ or 3.4+

Installation

To install a stable version from PyPi:

~$ pip install sbbst

Or download the __init__.py file directly from my GitHub and work with it.

The library works with the tree nodes defined as:

class TreeNode():
    def __init__ (self, val):
        self.val = val
        self.place = 0  # helps in the print process
        self.height = 1 # mandatory in the AVL Trees
        self.left = None
        self.right = None

Getting Started

To start working with the library, you will only need 2 lines:

>>> from sbbst import sbbst
>>> ST = sbbst()

And that will be enough to start working with it. Take the following script as an example

from sbbst import sbbst
ST = sbbst()
nums = [128, 131, 4, 134, 135, 10, 1, 3, 140, 14, 142, 145, 146, 147, 149] # random numbers
for num in nums:
    ST.insert(num)
# It also works out: ST = sbbst(nums)
print(ST)
print("Number of elements:",ST.getSize())
print("Height:",ST.getHeightTree())
print("Min val:",ST.getMinVal())
print("Max val:",ST.getMaxVal())
print("3rd smallest val:",ST.kthsmallest(3))
print("2nd largest val:",ST.kthlargest(2))
print("Pre Order:",ST.inOrder())
print("In Order:",ST.preOrder())
print("Post Order:",ST.postOrder())
ST.delete(128)
ST.delete(140)
print(ST)
ST.insert(55)
print(ST)
print("Number of elements:",ST.getSize())

This would be the output you will see in the terminal:

    ____128_________
   /                \
  _4             ___140___
 /  \           /         \
 1  10        134         145___
  \   \      /   \       /      \
  3   14   131   135   142      147
                               /   \
                             146   149

Number of elements: 15
Height: 5
Min val: 1
Max val: 149
3rd smallest val: 4
2nd largest val: 147
Pre Order: [1, 3, 4, 10, 14, 128, 131, 134, 135, 140, 142, 145, 146, 147, 149]
In Order: [128, 4, 1, 3, 10, 14, 140, 134, 131, 135, 145, 142, 147, 146, 149]
Post Order: [3, 1, 14, 10, 4, 131, 135, 134, 142, 146, 149, 147, 145, 140, 128]

    ____131______
   /             \
  _4          ___142______
 /  \        /            \
 1  10     134         ___147
  \   \       \       /      \
  3   14      135   145      149
                       \
                       146


    ______131______
   /               \
  _4__          ___142______
 /    \        /            \
 1    14     134         ___147
  \  /  \       \       /      \
  3 10  55      135   145      149
                         \
                         146

Number of elements: 14

Additionally, I added 3 extra functios (the 3 of them works in O(N) time) in case you want to use it along you practice coding in platforms such as LeetCode or Interviewbit. (At the beginning I had troubles to visualize what was happening in the Trees and the DFSs, swaps or insertions, so thats why I worked on in this library as sketch and then improved as it is today.) In those pages the input of the trees will be like:

s = "1 2 3 -1 4 -1 5 -1 -1 6 -1 -1 -1"
s = "1,2,3,null,4,null,5,null,null,6,null,null,null"
s = [ 1, 2, 3, None, 4, None, 5, None, None, 6, None, None, None ]

Some functions you can use are the following:

from sbbst import *
# Any of the following s works out
# s = "1 2 3 -1 4 -1 5 -1 -1 6 -1 -1 -1"
# s = "1 2 3 None 4 None 5 None None 6 None None None"
# s = "1,2,3,null,4,null,5,null,null,6,null,null,null"
s = [ 1, 2, 3, None, 4, None, 5, None, None, 6, None, None, None ]
head = getTree(s)
print(getStr(head))
print("The list of the Tree is:",getList(head))

The output in the terminal will be the following:

  _1
 /  \
 2  3_
  \   \
  4   5
     /
     6

The list of the Tree is: [1, 2, None, 4, None, None, 3, None, 5, 6, None, None, None]

Contributing

The best way to learn is to copy the code and edit it with your own necessities. You can also find other useful data structures in my GitHub https://github.com/Ualabi/Useful_Data_Structures.

If you want to contribute to this library, please do a pull request in the GitHub. Thanks!

Change Log

• 0.1 (09/09/2020)

  • First release

• 1.0 (19/10/2020)

  • Fix the counter of nodes in delete funcion. Spotted by DustinWehr .