Please enable JavaScript.
Coggle requires JavaScript to display documents.
Table ADT and Binary Search Trees (A Table ADT is useful to store vital …
Table ADT and Binary Search Trees
A Table ADT is useful to store vital
information (usually Statistical in nature)
Using a Table ADT, we want to efficiently obtain the following:
Search (T data)
Insert(T data)
FindMax()
FindMin()
ListDataInSortedOrder()
Remove(T data)
GetMedian()
Next(T data)
Previous(T data)
GetMean()
New Definition Unlocked: Dynamic Data Structure Operations
Meaning: It changes the Data contained in the Data Structure. E.g. Insert and Remove
Non-Dynamic Data Structures could be Searches/ Queries etc.
We will implement a Table ADT using
a Binary Search Tree Data Structure
Implement a Vertex Class (each Node of a
BST is an object of the Vertex Class)
Attributes:
Vertex left // the left child of this vertex
Vertex right // the right child of this vertex
Vertex parent // the parent of this vertex
T key / T data / T value // the value stored in this vertex
Create a BST Class
that has the following:
Attribute:
Vertex root;
Why?
Most Helper Functions start from Root so
we need to know where is the root.
Methods
:
search(int v)
O(h)
findMin()
O(h)
findMax()
O(h)
successor() findMin() in Right Subtree
O(h)
predecessor() - findMax() in Left Subtree
O(h)
insert(int v)
O(h)
(
Need to include repointing of references.
Having a boolean flag to avoid redundant pointing does not improve time complexity because checking for boolean and repointing are both O(1).
delete(int v)
O(h)
(Need to include repointing of references)
inorder()
O(n)
Rank(int v) //returns rank of vertex with value v
Select(int k) // returns value of kth smallest element
If Height is N (completely unbalanced), Complexity of every method is O(N). Therefore we need an AVL Tree to solve this problem
Properties of a Binary Search Tree Data Structure
For every vertex x, and y,
y.key < x.key if y is in left subtree of x
y.key >= x.key if x is in right subtree of x
Do note that keys that have equal value should be placed
right subtree
Drawback: For the same set of N keys, depending on order of insertion, we can get a BST of minimum height log N or a maximum height of N. We want to improve BSTs such that no matter how we insert keys, we will get a height of log N. How?
AVL TREES!