| A | B |
|---|
| Node | A node is a structured variable (or object) containing at least one field whose type is a pointer type. ( (A) ) |
| Root | The top node in a tree. |
| Parent | The converse notion of a child aka the Node above the current Node that is looked/ 15 to a 8 and or 10. |
| Child | A node directly connected to another node when moving away from the Root. |
| Sibling | A group of nodes with the same parent. |
| Descendant | A node reachable by repeated proceeding from parent to child. |
| Ancestor | A node reachable by repeated proceeding from child to parent. |
| Leaf | A node with no children. |
| Interior Node | A node of a tree that has one or more child nodes, equivalently, one that is not a lea |
| Subtree | The tree which is a child of a node |
| Path | A sequence of nodes and edges connecting a node with a descendant. |
| Level | The level of a node is defined by 1 + the number of connections between the node and the root. Level = Depth + 1 |
| Depth (of a Node) | The depth of a node is the number of edges from the tree's root node to the node. Depth = Level - 1 |
| Height (of a Node) | The height of a node is the number of edges on the longest path between that node and a leaf. |
| Binary Tree | A binary tree T is a finite set of nodes such that: T is empty, T consists of a root, R, and exactly two distinct binary trees: left subtree TL, and right subtree TR |
| Pre-order Tree Traversal | node, left, right |
| In-order Tree Traversal | left, node, right |
| Post-order Tree Traversal | left, right, node |
| Treesort | To sort a vector: Insert elements into BST, Retrieve them using in-order traversal. Worst case with vanilla BST?: O (N2 ), Average case?: O (N lg (N)). STL tree-based structures worst case?: O (N lg (N)) |
| Set | OAC Set maintains a collection of unique values called keys. Set A: 1, 2, etc. Set B: Buick, Honda, etc.Unorder Associative version does the same but it is not in order. No duplicates. |
| Map | OAC Map relates keys to values. A29-468 -> 8.75. Unordered Associative version doesn't have them ordered. No duplicates |
| Multiset | Set maintains a collection of unique values called keys but now with duplicates. Set A: 1, 2, etc. Set B: Buick, Honda, etc. Unordered Associative version does the same but it is not in order. |
| Multimap | Map relates keys to values with duplicates. A29-468 -> 8.75. Unordered Associative version doesn't have them ordered. |
| Base case for Trees | Tree is empty, don't do anything |
| Trees are used to implement | STL Ordered Associative Containers |
