Tree Type Definition Properties Advantages Disadvantages Applications Time complexities
Set of node and set of
directed edges that
Tree does not have cycles
Yes/ no decision making O(n) in the best,
process worst and average
An example of a data 1. Non-linear DS have more case. O(n) means
structure that is made efficient operations. that the running
Binary Tree time increases as
of linked nodes and is 2. Each node has a maximum of
non-linear two children the size of the
input increases.
n = the input size
1. Nodes must be comparable. Best case: O(1)
Lots of work
2. Nodes in the left subtree of a Average Case:
A binary tree with involved to
Binary Search Tree particular node < particular node. Fast search Any ordering of data O(h), which is
aditional properties add/ remove
3. Nodes in right subtree of a O(logn)
nodes
patricular node > particular node Worst case: O(n)
AVL trees are mostly used
for in-memory sorts of sets
Whatever the worst case and dictionaries. AVL trees
is, the tree is still are also used extensively in
Adding/
1. Every node must be balanced. balanced. Nodes are database applications in Worst case and
A BST with additional Removing
AVL Tree Height of left and right subtrees distributed to a larger average: O(log2n)
balancing properties nodes requires which insertions and
must differ by at most 1 degree. deletions are fewer but For space its O(n)
extra work
:. Tree height is SHORTER there are frequent lookups
:. Operations are FASTER for data required.
1. Every node is associated with a
colour
2. Every leaf nil is black
3. Root nodes are black
4. Every node inserted is red
5. Every inserted node is red
Weaker
6. If parent of new node is black,
balance All operations in
then exit. Fast insertions and
A BST with additional conditions than Good for schedulers, maps Best, average and
Red Black Tree 7. If parent of new node is red, retreivals. Same adv as
balancing properties AVL tree. One and sets. worst case take
then check the colour of the AVL tree.
bit per node for O(logn) time
parent's sibling of new node:
colour
a) If color is black or null then do
suitable rotation and recolour.
b) If colour is red then recolour and
check is parent's parent of new
node is not root node, then
recolour and recheck.
1. Limited in
Array is a limited size. Faster than
Data structures where 1. Array does not need to size (based on
a BST
items are stored in a be searched through arrays)
Item -> Index. Takes a particular
location determined by when the user searches 2. Can be
Hash Table item and computes the index in O(1) for all
their content. Content 2. In turn, this makes It resized but
the array that is associated with
based index rather than fast, efficient, should be
that item. Computes a location
comparison-based index inexpensive avoided.
where that item may be stored.
3. Hard to order
Doesn’t
Helps calculate the best account for
Hash Function 1 index an item should go hash(x) = x % table size order of input.
in Results in
collisions
Solves uniqueness
Hash Function 2 hash(x) = (((a)*37 + b) * 37 + c) problem by multiplying/
shifting each character by
some value
A class of algorithms.
We figure out the 1. Linear Probing: Inserting into
position the item should next position available
Open addressing
go into the array, but is 2. Quadratic probing: Avoids
not fixed. It is a first clustering of linear probing
guess
Chaining: Creates a structure n = items, m =
We find a position in attached to every position within table size
Closed Addressing the array and do not the array. Usually a linked list, Best Case: O(n/m)
deviate within the array. something with a table of pointers Average case: 1/2
and references x n/m
Worst case: O(n)
Set of node and set of
directed edges that
Tree does not have cycles
Yes/ no decision making O(n) in the best,
process worst and average
An example of a data 1. Non-linear DS have more case. O(n) means
structure that is made efficient operations. that the running
Binary Tree time increases as
of linked nodes and is 2. Each node has a maximum of
non-linear two children the size of the
input increases.
n = the input size
1. Nodes must be comparable. Best case: O(1)
Lots of work
2. Nodes in the left subtree of a Average Case:
A binary tree with involved to
Binary Search Tree particular node < particular node. Fast search Any ordering of data O(h), which is
aditional properties add/ remove
3. Nodes in right subtree of a O(logn)
nodes
patricular node > particular node Worst case: O(n)
AVL trees are mostly used
for in-memory sorts of sets
Whatever the worst case and dictionaries. AVL trees
is, the tree is still are also used extensively in
Adding/
1. Every node must be balanced. balanced. Nodes are database applications in Worst case and
A BST with additional Removing
AVL Tree Height of left and right subtrees distributed to a larger average: O(log2n)
balancing properties nodes requires which insertions and
must differ by at most 1 degree. deletions are fewer but For space its O(n)
extra work
:. Tree height is SHORTER there are frequent lookups
:. Operations are FASTER for data required.
1. Every node is associated with a
colour
2. Every leaf nil is black
3. Root nodes are black
4. Every node inserted is red
5. Every inserted node is red
Weaker
6. If parent of new node is black,
balance All operations in
then exit. Fast insertions and
A BST with additional conditions than Good for schedulers, maps Best, average and
Red Black Tree 7. If parent of new node is red, retreivals. Same adv as
balancing properties AVL tree. One and sets. worst case take
then check the colour of the AVL tree.
bit per node for O(logn) time
parent's sibling of new node:
colour
a) If color is black or null then do
suitable rotation and recolour.
b) If colour is red then recolour and
check is parent's parent of new
node is not root node, then
recolour and recheck.
1. Limited in
Array is a limited size. Faster than
Data structures where 1. Array does not need to size (based on
a BST
items are stored in a be searched through arrays)
Item -> Index. Takes a particular
location determined by when the user searches 2. Can be
Hash Table item and computes the index in O(1) for all
their content. Content 2. In turn, this makes It resized but
the array that is associated with
based index rather than fast, efficient, should be
that item. Computes a location
comparison-based index inexpensive avoided.
where that item may be stored.
3. Hard to order
Doesn’t
Helps calculate the best account for
Hash Function 1 index an item should go hash(x) = x % table size order of input.
in Results in
collisions
Solves uniqueness
Hash Function 2 hash(x) = (((a)*37 + b) * 37 + c) problem by multiplying/
shifting each character by
some value
A class of algorithms.
We figure out the 1. Linear Probing: Inserting into
position the item should next position available
Open addressing
go into the array, but is 2. Quadratic probing: Avoids
not fixed. It is a first clustering of linear probing
guess
Chaining: Creates a structure n = items, m =
We find a position in attached to every position within table size
Closed Addressing the array and do not the array. Usually a linked list, Best Case: O(n/m)
deviate within the array. something with a table of pointers Average case: 1/2
and references x n/m
Worst case: O(n)
