RedBlack tree

represent 2-3-4 trees as BST with red&black nodes

Red&Black node로 BST(binary search tree)같은 2-3-4트리를 구현할 수 있다.

root always black

루트는 항상 black

-never two red nodes in a row

한열에 두개의 red node가 있을 수 없다

-For each node, all simple paths from the node to descendent leaves contain the same number of black nodes

각 노드에 대하여 노드에서 자식 leave까지의 simple path에는 동일 한 수의 black node가 포함된다

2-3-4 tree    ->    red black tre

동그라미 두번친게 red node

black height

1. Insertion : insert as a red node

Case 1) z=red, z.p=red, y=red

Case 2) z=red, z.p=red y=black

Case3) z=red, z.p=red, y=black

Case4) z=red zp=black z=root

정리 더 잘된 블로그 ㅠ

http://ddmix.blogspot.kr/2015/02/cppalgo-19-red-black-tree.html

http://egloos.zum.com/sweeper/v/900135