SHARE

TWEET

# Untitled

a guest
Jul 22nd, 2019
49
Never

**Not a member of Pastebin yet?**

**, it unlocks many cool features!**

__Sign Up__- ### List:
- node1 -> node2 -> node3
- ### Tree:
- node1 -> node2
- -> node3
- -> node4
- ### Binary Trees:
- node1 -> left_node (child)
- -> right_node (child)
- ``` C
- typedef struct nodeBtree {
- int data;
- struct nodeBtree *left;
- struct nodeBtree *right;
- } Node;
- ```
- The top most node of a tree is called the root node.
- Nodes at the same height in the tree are said to be in the same level in the tree: level 0, level 1, ...
- Nodes with no children nodes are called leaf nodes.
- ### Binary Search Tree (BST):
- - A tree such that at every node, if a value (key) is <= value (key) in the node, then that key must be stored somewhere on the left sub-tree
- otherwise, store in the right sub-tree
- - On average, BST search is O(log2 N).
- - BST insert (key, root):
- - if root is NULL, new node becomes root
- - else compare key against root -> key
- if less or equal, insert(key, +/- -> left)
- else insert(key, root -> right)
- - if BST is fully packed, every single level, except for the last level are fully filled in.
- - a full BST can hold up to N keys in a tree of height O(log2 N) -- every level duplicates the capacity of the BST
- - when do I expect close to packed BST full? If keys in random order
- - when the keys are sorted, O(N)
- - with the key, we want to unqiuely identify each node
- ### BST Delete
- - node w/ no children:
- - search: find the node with the key to delete
- - set parent link to NULL
- - free the node
- - node with 1 child:
- - search:
- - link parent node to granchild node
- - free the node
- - node with 2 child:
- - search:
- - promote smallest key on the right side
- - delete the old node for the smallest key (hold on to the reference after promoting)
- OR
- - promote the largest key on the left side
- - delete the old node for the largest key (hold on to the reference after promoting)
- ### BST Traversal
- - in-order traversal: left, then middle, then right to produce an ascending order list of keys -- reverse order if you want descending order
- - algorithm:
- - do in-order traversal of left node
- - apply operation on this node, i.e. print() -- print value of all nodes
- - do in-order traversal of of right sub-tree
- - order of complexity: Traversal (in-order) on average -> O(N) + Building BST: insert() -> O(N log N)
- - pre-order traversal:
- - algorithm:
- - apply operation to middle node
- - pre-order traversal on left sub tree
- - pre-order traversal on right sub tree
- - you preserve the order of the BST when you copy it
- - order of complexity: compilers and NLP
- - post-order traversal:
- - algorithm:
- - post-order traversal left sub tree
- - post-order traversal right sub tree
- - apply operation to middle node
- - Delete BST application
- - Just a traversal, you get a free step since you delete as you go and never touch the node again, O(N)
- **********************
- # Graphs & Recursion
- ### Graph -> Set of Nodes/Vertices (V)
- - represents data in your collection
- - Nodes: represented with a circle w/ an index and a bunch of data
- - Edges: connections between nodes - represent relationship between data items
- ### Types of Graphs:
- - Undirected graph: social networks like facebook
- - relationship is both-ways
- - Directed graphs:
- - hierarchical relationship
- - no link backs, one way
- ### Neighbourhood of a node:
- - nodes connected to 'this' one
- - out-neighbourhood: edges from 'this' node to others
- - in-neighbourhood: edges arriving at 'this' node
- - who are neighbours? who are my neighbours' neighbours?
- - degree: # of nodes in the neighbourhood
- - out-degree: children in geneology
- - in-degree: parents in geneology
- ### Path:
- - through a graph, a series or sequence of nodes that are visited from the start node to an end node
- ### Cycle:
- - in a path... a path with at least 3 nodes that starts and ends at the same node for unidrected graphs
- - in a directed graph, the minimum number of nodes is 1.
- ### Graph Representation:
- - need to store V: LL, BST, array
- - ways to store edges:
- - option A: Adjacency list (storing E)
- - Array of one entry per node
- - Each entry has a pointer to a linked list of connections
- - For directed graphs, if node A and B are connected, you will find entries of each other in their edge list
- - Edge query is O(N)
- - option B: Adjecency Matrix
- - Array of arrays, n x n matrix
- - 0 or 1 depending on whether the nodes are connected or not
- - Edge query O(1)

RAW Paste Data

We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.