NOTES.txt

BINARY TREE

	Full
		Leaves have no children
		Nodes that do have children, have 2 children
	Complete
		Like binary heaps
		Fill out top to bottom, left to right
	Perfect
		Both complete and FULL
		All leaves are on the same level

	Traversals

		N = Node, L = Left, R = Right
		Preorder
			N L R
		Inorder
			L N R
		Postorder
			L R N


AVL TREES

	COURSE:
		https://www.youtube.com/watch?v=FNeL18KsWPc

	Visualized:
		https://www.cs.usfca.edu/~galles/visualization/AVLtree.html


	Threshold: used to determine when to rebalance tree

	Every node roots it's own subtree
	Has a subtree to the left and to the right

	Height:
		H: -1 (EMPTY)
		H:  0 (SINGLE NODE)
		H: max(H(L), H(R)) + 1
	
	Balance:
	
		Balance(node) = Height(Left) - Height(Right)

		Standard threshold = 1
		Goal of AVL: keep |Balance(node)| <= Threshold
	
			LEFT-HEAVY: B(n) > 0 (positive balance)
		RIGHT-HEAVY: B(n) < 0 (negative balance)
	
	Rotations:

		Rotations fix imbalance

		Left-Heavy:
			(1) Right rotation
			(2) Left-Right rotation
		Right-Heavy:
			(1) Left rotation
			(2) Right-Left rotation
	
	Insertion:

		1. Standard BST insert
		2. Fix AVL property

		imbalance(x)
			if (rightHeavy(x)) is RIGHT HEAVY
				if (rightChild is rightHeavy or balanced) {
					LR(x)
				}
				else {
					RR(y)
					LR(x)
				}

			else if (leftHeavy(x))
				if (leftChild is leftHeavy or balanced) {
					RR(x)
				}
				else {
					LR(y)
					RR(x)
				}
	Deletion:

		if no child
			return NULL
		if one child
			return child
		if two children
			swap predecessor of inorder (max of left subtree)
			delete node in it's new location (can't have 2 children now)
			update height (by going up to all parents)
			check balance of CUR node, and up the callstack

Red-Black Trees

	Visualized:

		https://www.cs.usfca.edu/~galles/visualization/RedBlack.html

	https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-046j-introduction-to-algorithms-sma-5503-fall-2005/video-lectures/lecture-10-red-black-trees-rotations-insertions-deletions/

	https://www.codesdope.com/course/data-structures-red-black-trees/
	https://www.codesdope.com/course/data-structures-red-black-trees-deletion/
	https://en.wikipedia.org/wiki/Red%E2%80%93black_tree

	Intro to algo:
		PRE: P.23
		RBT: P.308

	Invariant:

		1. Every node has a colour either red or black.
		2. The root of the tree is always black.
		3. All leaves are black
		4. There are no two adjacent red nodes (A red node cannot have a red parent or red child).
		5. Every path from a node (including root) to any of its descendants NULL nodes has the same number of black nodes.

	Insertion

		- BST Operation
		- Set color to red
		- Fix the Red-Black property violation (if any)

		Insert(x) {
			bstInsert(x);
			x->color = red;
			fixProperty(x);
		}

		fixProperty(x) {

			while (x->parent == red) {
				if (uncle == red) {
					// case 1
					uncle = black;
					parent = black;
					grandparent = red;

					// grandparent might be in violation so we have to check it
					x = grandparent;
				} else {
					if (x == leftChild) {
						// case 2
						rotateLeft(parent);
						x = parent;
					}
					// case 3 (and 2.5)
					swap(parent->color, grandparent->color);
					rotateRight(grandParent);
				}
			}
			// In case the color of the root changed
			root = black;
		}

Tree Structure

	Types:
		iterator
		const_iterator
	
	Constructors/Destructors:
		Tree(const value_compare& comp);
		Tree(const Tree& from)
		~Tree();
		Tree& operator=(const Tree& x);

	Iterators:
		iterator begin();
		const_iterator begin() const;

		iterator end();
		const_iterator end() const;
	
	Capacity:
		size()
		max_size()
	
	Modifiers:
		iterator insert(const value_type& val);
		iterator insert(iterator position, const value_type& val);

		void erase(const value_type& val);
		void erase(iterator position);

		void swap(TreeRB& x);
		void clear();
	
	Observers:

		value_compare value_comp() const;
	
	Operations

		iterator find(const value_type& val);
		const_iterator find(const value_type& val) const;

		size_type count(const value_type& val) const;

		iterator lower_bound(const value_type& k);
		const_iterator lower_bound(const value_type& k) const;

		iterator upper_bound(const value_type& k);
		const_iterator upper_bound(const value_type& k) const;

		ft::pair<iterator, iterator> equal_range(const value_type& val);
		ft::pair<const_iterator, const_iterator> equal_range(const value_type& val) const;