self-balancing-binary-search-tree 0.1.4

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 SBBSTs (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:

I made the library self_balancing_binary_search_tree (sorry for the long name, though there is a shorter implementation here) 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 self_balancing_binary_search_tree

Or just

~$ pip install sbbst

Or download the __init__.py file directly from my GitHub and worh 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 self_balancing_binary_search_tree import SBBST
>>> ST = SBBST()

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

from self_balancing_binary_search_tree 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 lasrgets val: 145
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    14       134      145
  \  /  \         \        \
  3 10  21        135      149
          \
          50


    __________131______
   /                   \
  _4__              ___142
 /    \            /      \
 1    14__       134      145
  \  /    \         \        \
  3 10    50        135      149
         /  \
        21  55

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 self_balancing_binary_search_tree 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 take a look at this page before submitting a pull request. Thanks!

Change Log

• 0.1.4 (09/09/2020)

  • First tries and fails