source: cs50
Showing posts with label algorithms. Show all posts
Showing posts with label algorithms. Show all posts
Wednesday, March 10, 2021
trie (comes from the word "retrieve") - actually a tree made up of arrays
a tree whose nodes are each arrays
and each of those arrays are arrays of pointers to other nodes
constant time lookups and insertions
if someone's name has 200 letters , lookup time would be big O of (200)
it doesnt matter how many names are in the trie data structure (1 billion, 2 billion, 3 billion), lookup time only depends on number of letters in name
tries give you the holy grail of constant time
source: cs50.
Monday, March 8, 2021
avl trees , red black trees - built-in balancing mechanisms
algorithms for shifting while inserting or deleting built in to keep binary tree "logarithmic in height" rather than "linear in height"
inserting into a balanced binary tree is indeed big O of logn , but that depends on the prerequisite of you keeping the binary search tree balanced
source: cs50
Data structures comparison - arrays, linked lists, hash tables, tries
Arrays:
- insertion is bad - lots of shifting to fit an element in the middle (except for inserting at the end of the array, anywhere other than the end of the array is not so great)
- deletion is bad - lots of shifting after removing an element (except for deleting from the end of the array, unless we don't care about leaving empty gaps, which we usually don't want)
- lookup is great - random access, constant time
- relatively easy to sort
- relatively small size-wise
- stuck with a fixed size, no flexibility
Linked lists:
- insertion is easy - just tack onto the front
- deletion is easy - once you find the element
- lookup is bad - have to rely on linear search
- relatively difficult to sort - unless you are willing to compromise on super-fast insertion and instead sort as you construct
- relatively small size-wise
Hash tables:
- insertion is a two-step process - hash, and then add
- deletion is easy - once you find the element
- lookup is on average better than with linked lists because you have the benefit of a real-world constant factor
- not an ideal data structure if sorting is the goal - just use an array
- can run the gamut of size
source: harvard cs50 david malan
what is the running time of inserting into a binary search tree?
big O of logn
things related to binary search are often big O of logn
if you have a well-balanced binary tree, if it has a total of n nodes, then log-based-2-of-n will be the height of the tree
source: harvard, cs50, david malan
Sunday, March 7, 2021
code for searching binary search tree (BST)
bool search (node *tree, int number)
{
//always check for NULL when dealing with pointers
//this is also the base case
if (tree==NULL)
{
return false;
}
//
elseif (number < tree->number)
{
return search (tree->left, number);
}
elseif (number > tree->number)
{
return search (tree->right, number);
}
elseif (number == tree->number)
{
true;
}
}
video location: lecture 5. 1:20:00 ~ 1:30:00
source: harvard cs50, david malan
]
code for creating node for binary search tree (BST)
typedef struct node
{
int number;
struct node *left;
struct node *right;
}node;
source: harvard cs50, david malan
binary search tree (BST)
requires array in sorted order
requires random access of arrays
very powerful because big O of logn
location in week 5 video: 1:20:00
source: harvard cs50, david malan
Subscribe to:
Posts (Atom)