• API
• FAQ
• Tools
• Archive
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.

Top