W1-Binary Tree And RedBlack Tree

Binary Tree¶

The Property of Binary Search Trees¶

1. Every node, except leaf, (internal node) have two children
2. The key of left child (as well as nodes of left sub-tree) ≤ The key of parent ≤ The key of right child (as well as nodes of right sub-tree)

• Quiz

3. The height of node h is $log_{2}⁡n≤h≤n$

• Quiz

Tree Traversal¶

1. In-order traversal
	a. left→self→right
	b. 12,18,20,29,30,31,32,33,34
	c. Sorted order
2. Pre-order traversal
	a. self→left→right
	b. 35,29,18,12,20,32,31,30,34,33
3. Post-order traversal
	a. left→right→self
	b. 12,20,18,30,31,33,34,32
    

• Demonstration
  

Red Black Tree¶

Why we need it?¶

1. When we insert node into binary search tree in a bad order, it will produce a very unbalanced tree    
	a. Solution: Self balancing tree   
		1. Red-Black Tree
		2. 2-3 Tree
		3. Splay Tree
		4. AVL Tree
		5. Skip Lists 
		6. B-Tree
		7. Treaps!

Red-Black Tree¶

1. Still have BST property
2. Every node have color information
	a. Red
		1. Every red node must have black children
		
	b. Black
		1. Root and leaves are black
		2. The number of black nodes on any path from any node to a leaf must be the same. (Black Height)

• Demo
  

• Quiz

The height h of root in the red-black tree is between $ log_{2}n≤h≤2(log_{2}⁡n) $

Maintain the property of red-black trees (insertion and deletion)¶

1. Find(key)
	a. Exact same as  binary search tree (O(log_2⁡n))
2. Insert(key) (O(log_2⁡n))
	a. The insert node is always been colored red (replace a leaf)

		i. If the parent of the node is black, then everything is fine, black height remains same
		ii. If the parent node is red, then we have red-red violation. 
			1) If the insert node have a red "uncle" (w), we re-paint the tree, change z (grandparent) to red, and y,w to black
				1) If z's parent is red, recursively call this approach

			2) When "uncle(w)"  is black, we do "tree rotation"
				1) If insert node x < parent node y

				2) If insert node x > parent node y
					1) We do left rotation between x and y
					2) Then do right rotation as above

Tree rotation¶

1. Right Rotation

2. Left Rotation

• Quiz

Skip List¶

Definition¶

Property¶

	a. Alternative structure of balance binary tree
		i. Insert
		ii. Search
			1) Use O(1) to find the minimum and maximum
		iii. Delete
		iv. Iterate through all items in sorted order
	b. Randomized data structure (use probability)
		i. Provide Probabilistic guarantees
		ii. Elegant approach to data structure design
        

Basic Idea¶

	a. If we want to go to a station that local train do not arrive, we should
		i. Take express to nearest station
		ii. Take a local train remainder of the way
	b. Skip list just born from this idea
	c. It contains muti-lists, each list(Layer) is sorted. Each node have pointer to both next node and node below

Example¶

If we want to find 22, we start from the left top, our path is −∞→12→12→12→12→18→22¶