Please enable JavaScript.
Coggle requires JavaScript to display documents.
Binary Search Tree - Coggle Diagram
Binary Search Tree
Balancing BST
AVL
Splay
Idea is that we wan the items we search more frequently close to root so that we find them faster
But as we dont know before hand whcih items will be serched more want to do it dynamically
Splay operation to get the node to the root
Trepes
RedBlack Trees
NOTE: they are all different ways to get balanced BST
Problems that can be solved efficiently using BST
Local Search
What it is ? why local
Local ?
Local search means that we are looking around something locally like looking for the nearest neighbors or elements within a range
Local Search Data structure
Operations
Insert element with a key
similarly delete
RangeSerach(x,y)
Nearest Neighbor on both sides
DS store elements that have keys which can be ordered
Where do we do local search
Nearest Neighbors
Dictionary
heights
Range
Emails or messages that came within a period time
Balanced BST(AVLtrees)
Have a measure of the balance
Compare the heights
AVL tree property for all nodes the absolute value of the difference between the height of its left and right subtree is at most 1
Given x find all the ellements less than x and all the elements which are greater than x
You just cannot say that all the elments greter than x are in its right subtree and all elements smaller than x are in its left subtree (THISONLY WORKS IF X IS ROOT) IN genrral to find this you have to look at the left ancestors and the right anscestoirs
Many operations in BST can be understood by binary serach on array analogy