bintree notes 2 and pattern matching

Binary Search Tree--
Left side is strictly less than node; right strictly greater
All leaves must also be binary search trees

Pattern matching-- the match thing; see the bintree file in notes

case class Bst(left: Bst[Int], item: Int, right: Bst[Int])
this is a way to make one where you can do shit like
	tree.item

instead of using pattern matching

==========

red black tree (balanced binary search tree)

this is a bst where every node is colored red or black
criteria for binary search tree still apply

THE RULES (VERY IMPORTANT):
	Red Rule: Every red node has a black parent.
	Black Rule: Every path from root to bottom has the same number of black nodes.

If it's missing one or both children it's considered a bottom node.

It is the colors that enforce the balance
- Balanced to within factor of 2-- shortest path 3 longest path 6 for example
- shortest path black black black, longest black red black red black red etc (so it's x2)

Enough to guarantee height is O(logN)

===

Searching is easy-- ignore colors and search like normal BST

Insert-- starts out easy; insert like ordinary BST and color the node red
- Always color the node red

but what if inserting it fails the red rule?
If you have a red node with a red parent, take the red node and the black grandparent and rearrange / recolor as red parent, two black children-- the rearranging is such that the "middle" node is the parent so that you can fulfill the proper format of parent, less than, greater than

Rebalancing practice

You can rebalance more than once
how the heckity heck do you do this in code though