Skip to content

Maheshkumar-novice/Binary-Search-Tree

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

59 Commits
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

Table Of Contents
  1. Description
  2. Variations
  3. Applications
  4. Built With
  5. What I Learned
  6. Acknowledgements

Demo Demo Demo Demo

Description

In computer science, a binary search tree (BST), also called an ordered or sorted binary tree, is a rooted binary tree data structure whose internal nodes each store a key greater than all the keys in the node’s left subtree and less than those in its right subtree. A binary tree is a type of data structure for storing data such as numbers in an organized way. Binary search trees allow binary search for fast lookup, addition and removal of data items, and can be used to implement dynamic sets and lookup tables. - Wikipedia

BST

Binary Search Tree is a data structure where each root node's left subtree contains values lesser than the root node's value and right subtree contains values greater than the root node's value. Binary Search - Where we omit half the size of the problem on each iteration to find the solution. We start from middle of the collection of course. In binary search trees the root node will be the middle element of the collection. The root node's left child will be the middle element of the left half of the collection and the right child will be the middle element of the right half of the collection and it continues recursively until all the nodes are in the tree structure. It will be easier look for values in the binary search tree because every node's value will be greater than the left subtree and lesser than the right subtree.

Balanced BST

Balanced Binary Search Tree is a Binary Search Tree with the left and right subtrees' height difference must not exceed 1, recursively of course.

Height and Depth

  • Height of a node in a Binary Search Tree is the number edges from a node to the farthest leaf it can reach
  • Height of the tree with 1 node is 0
  • Depth of a node in a Binary Search Tree is the number edges from the root node to the given node
  • Depth of a root node is 0
  • Height of root node = Height of the tree = Max Depth of the Tree

Traversal

  • Breadth First
    • Level-Order Traversal
  • Depth First
    • Pre-Order
    • In-Order
    • Post-Order

Methods In This Implementation

Method Name Description
Node#new Creates New node with data, left, right
Node#<=> Compare node data to the other value
Node#to_s Prints the data
Tree#new Creates New BST with the given array
Tree#insert Inserts a Node to the BST
Tree#delete Deletes a Node from the BST
Tree#find Finds the value from the BST
Tree#level_order Level Order Traversal
Tree#preorder Pre Order Traversal
Tree#inorder In Order Traversal
Tree#postorder Post Order Traversal
Tree#balanced? Check if the BST is balanced or not
Tree#rebalance Rebalance the BST
Tree#to_s Prints the BST

Variations

Above are the two common self-balancing BSTs, they allow us to optimize the height of BSTs with minimum height possible.

Applications

  • Search Algorithms
  • Maintaining Sorted Data
  • Indexing
  • And so on...

Built With

  • Ruby

What I Learned

  • About Binary Search Trees
  • How to create a Binary Search Tree
  • How to use a Binary Search Tree
  • Operations on a Binary Search Tree
  • Understood recursion much more effectively
  • How to approach the problem when we stuck

Acknowledgements

Move To Top