SHARE
TWEET

Untitled

a guest Jul 22nd, 2019 49 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. ### List:
  2.     node1 -> node2 -> node3
  3.  
  4. ### Tree:
  5.     node1 -> node2
  6.           -> node3
  7.           -> node4
  8.  
  9. ### Binary Trees:
  10.     node1 -> left_node (child)
  11.           -> right_node (child)
  12.  
  13. ``` C
  14. typedef struct nodeBtree {
  15.     int data;
  16.     struct nodeBtree *left;
  17.     struct nodeBtree *right;
  18. } Node;
  19. ```
  20.  
  21. The top most node of a tree is called the root node.
  22. Nodes at the same height in the tree are said to be in the same level in the tree: level 0, level 1, ...
  23. Nodes with no children nodes are called leaf nodes.
  24.  
  25. ### Binary Search Tree (BST):
  26. - 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
  27.   otherwise, store in the right sub-tree
  28.  
  29. - On average, BST search is O(log2 N).
  30.  
  31. - BST insert (key, root):
  32.     - if root is NULL, new node becomes root
  33.     - else compare key against root -> key
  34.         if less or equal, insert(key, +/- -> left)
  35.         else insert(key, root -> right)
  36.  
  37. - if BST is fully packed, every single level, except for the last level are fully filled in.
  38. - 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
  39. - when do I expect close to packed BST full? If keys in random order
  40. - when the keys are sorted, O(N)
  41. - with the key, we want to unqiuely identify each node
  42.  
  43.  
  44. ### BST Delete
  45. - node w/ no children:
  46.     - search: find the node with the key to delete
  47.         - set parent link to NULL
  48.         - free the node
  49. - node with 1 child:
  50.     - search:
  51.         - link parent node to granchild node
  52.         - free the node
  53. - node with 2 child:
  54.     - search:
  55.         - promote smallest key on the right side
  56.         - delete the old node for the smallest key (hold on to the reference after promoting)
  57.         OR
  58.         - promote the largest key on the left side
  59.         - delete the old node for the largest key (hold on to the reference after promoting)
  60.  
  61.  
  62. ### BST Traversal
  63. - in-order traversal: left, then middle, then right to produce an ascending order list of keys -- reverse order if you want descending order
  64.     - algorithm:
  65.         - do in-order traversal of left node
  66.         - apply operation on this node, i.e. print() -- print value of all nodes
  67.         - do in-order traversal of of right sub-tree
  68.     - order of complexity: Traversal (in-order) on average -> O(N) + Building BST: insert() -> O(N log N)
  69. - pre-order traversal:
  70.     - algorithm:
  71.         - apply operation to middle node
  72.         - pre-order traversal on left sub tree
  73.         - pre-order traversal on right sub tree
  74.     - you preserve the order of the BST when you copy it
  75.     - order of complexity: compilers and NLP
  76. - post-order traversal:
  77.     - algorithm:
  78.         - post-order traversal left sub tree
  79.         - post-order traversal right sub tree
  80.         - apply operation to middle node
  81.     - Delete BST application
  82.     - Just a traversal, you get a free step since you delete as you go and never touch the node again, O(N)
  83.  
  84. **********************
  85.  
  86. # Graphs & Recursion
  87.  
  88. ### Graph -> Set of Nodes/Vertices (V)
  89. - represents data in your collection
  90.     - Nodes: represented with a circle w/ an index and a bunch of data
  91.     - Edges: connections between nodes - represent relationship between data items
  92.  
  93. ### Types of Graphs:
  94. - Undirected graph: social networks like facebook
  95.     - relationship is both-ways
  96. - Directed graphs:
  97.     - hierarchical relationship
  98.     - no link backs, one way
  99.  
  100.  
  101. ### Neighbourhood of a node:
  102. - nodes connected to 'this' one
  103. - out-neighbourhood: edges from 'this' node to others
  104. - in-neighbourhood: edges arriving at 'this' node
  105.  
  106. - who are neighbours? who are my neighbours' neighbours?
  107. - degree: # of nodes in the neighbourhood
  108.     - out-degree: children in geneology
  109.     - in-degree: parents in geneology
  110.  
  111. ### Path:
  112. - through a graph, a series or sequence of nodes that are visited from the start node to an end node
  113.  
  114. ### Cycle:
  115. - in a path... a path with at least 3 nodes that starts and ends at the same node for unidrected graphs
  116. - in a directed graph, the minimum number of nodes is 1.
  117.  
  118. ### Graph Representation:
  119. - need to store V: LL, BST, array
  120. - ways to store edges:
  121.     - option A: Adjacency list (storing E)
  122.         - Array of one entry per node
  123.         - Each entry has a pointer to a linked list of connections
  124.         - For directed graphs, if node A and B are connected, you will find entries of each other in their edge list
  125.         - Edge query is O(N)
  126.     - option B: Adjecency Matrix
  127.         - Array of arrays, n x n matrix
  128.         - 0 or 1 depending on whether the nodes are connected or not
  129.         - 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. OK, I Understand
 
Top