hash table - array of linked lists

 

source: cs50 

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. 

what is the running time for looking up a hash table

big O of (n)

source: cs50

(trees) vs (binary trees) vs (binary search trees) in computer science

 not completely the same

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

sorting algorithms - bubble sort, insertion sort, selection sort, merge sort

  source: harvard 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

linked list - big O of n

 

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

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

code for creating a node for a linked list

 typedef struct node

{

        int number;

        struct node *next;

}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