Data Structures 6 Flashcards
Binary Search tree
all left descendants < =n < all right descendents 8 / \ 4 10/ \ \2 6 20
Balanced Trees
AVL trees and red-black trees
Complete Binary Trees
“every level of the tree is fully filled, except for the last level. it has to be filled left to right “
Full Binary Tree
a binary tree where every node has zero or 2 children. It is the all or nothing binary tree
Perfect Binary Tree
It is both full and complete. 2k - 1 nodes where k is the height
In-Order Traversal
LDR -> Left, Visit Node, Right.
Pre-Order Traversal
DLR -> Visit Node, Left, Right
Post-Order Traversal
LRD -> Left, Right, Visit NOde
Array advantages
Simple and easy to use and access to elements is O(1)
Array disadvantages
fixed size, one block allocation, and complex position-based insertion
O(1) complexity for access
Array and dynamic arrays time complexity.
O(n) time complexity for accessing elements
lists
Main operations of lists
traversing, insert(), pop()
Main operations of stack
push(), int pop()
Auxiliary operations of stack
int top(), int size(), int empty(), isFull()
I want to balance symbols, tags, and fix symbols
stack applications
Space complexity of stack
O(n)
Time complexity of push, pop, and operation of stack
O(1)
Why is the push implementation of a dynamic array and list Average O(1)
Every now and then we have to increase the size of a full array which involves an O(n) operation
idempotent
doing the same operation multiple times and getting the same outcome. In terms of Restful services, I should do the same call on data, multiple times, and it will not change.
GET request
It is idempotent, therefore, It should never be used to alter data. We would like to be able to do this over and over
PUT request
It is idempotent, therefore, it should only be used to update data. If I update with the same information, the result will not change.
POST request
It is not idempotent, therefore, it should be used to alter data in some form where if you did the same post request, the resulting set will be different.
CRUD
Create, Read, Update, Delete
One-Many or Many One ->
In objects, if one object can have many of another object.This can be done with a simple WHERE clause or a simple join if another column data is needed of some sort
Many-Many
If Many objects can have many of another. An employee can be a part of many departments, while many departments can have many employees. This is normally done by an intermediate table.
