|Data Structure||Dynamic Array||Self-Balancing BST||Doubly-Linked List||Self-Balancing BST||Hash Table|
|Data Structure||Virtual Method Table (vtable)|
How does dynamic array allocate memory dynamically (growing & shrinking in run time)?
|Binary Tree||Binary Search Tree|
|A tree data structure in which each node has at most two child nodes.||An ordered or sorted binary tree, with no duplicate nodes.|
|A dynamic array, like C array (i.e., capable of random access) with the ability to resize itself automatically when inserting or erasing an object. Inserting and removing an element to/from back of the vector at the end takes amortized constant time. Inserting and erasing at the beginning or in the middle is linear in time.||A doubly linked list; elements are not stored in contiguous memory. Opposite performance from a vector. Slow lookup and access (linear time), but once a position has been found, quick insertion and deletion (constant time).|
Different types of traversal in Binary trees
1 Depth-first traversal
1a. pre-order traversal
1b. post-order traversal
2 Breadth-first traversal
|Best Performance, O(1)||Average Performance, O(log n)||Worst Performance, O(n)|
|Binary Tree Structure||When one searches the root node||When you search a normal BST||When the unbalanced tree resembles a linked list (degenerate tree).|
|Abstract Class||Singleton Class|
Example scenarios why & when would we need derived classes
Because we have access to the source code of the Base class, we could add functionality directly to Base. However, there may be times when we do not want to, or can not. Consider the case where you have just purchased a library of code from a 3rd party vendor, but need some extra functionality. You could add to the original code, but this isn’t the best solution. What if the vendor sends you an update? Either your additions will be overwritten, or you’ll have to manually migrate them. It’s also common to for developers to release header files containing class definitions, but release the implementation code precompiled — this means you can use the code, but you won’t have the ability to modify it directly.
In either case, the best answer is to derive your own class, and add the functionality you want to the derived class.