흑적나무 ( red-black tree )

주제(Subject)
--------------------------------------------------------
한글(약어) : 흑적나무()
영어(약어) : red-black tree()


관련개념(Related Concepts)
--------------------------------------------------------
2-3-4나무
탐색
알고리즘


개요(Summary)
--------------------------------------------------------
2-3-4나무를 이진탐색나무 형태로 구현한 것.

The original structure was invented in 1972 by Rudolf Bayer who called them "symmetric binary B-trees", but acquired its modern name in a paper in 1978 by Leo J. Guibas and Robert Sedgewick. It is complex, but has good worst-case running time for its operations and is efficient in practice: it can search, insert, and delete in O(log n) time, where n is the number of elements in the tree.
                                                                             - Wikipedia : red-black tree

본문(Body)
--------------------------------------------------------
1. 흑적나무의 성질

- Every node has two children, each colored either red or black.
- Every tree leaf node is colored black.
- Every red node has both of its children colored black.
- Every path from the root to a tree leaf contains the same number (the "black-height") of black nodes.
                                                                           - Mathworld : Red-black tree

2. 연산
   1) 삽입연산시 회전, 분할이 필요함
      (1) 색(tag) 변경
      (2) 색(tag) 변경 후 회전
      (3) 색(tag) 변경 후 이중회전

3. 시뮬레이션
   1) Red/Black Tree Demonstration
      http://www.ececs.uc.edu/~franco/C321/html/RedBlack/redblack.html

   2) AVL tree applet
      http://webpages.ull.es/users/jriera/Docencia/AVL/AVL%20tree%20applet.htm


모임,단체(Commutities)
--------------------------------------------------------


블로그,개인 홈페이지 등(Humanities)
--------------------------------------------------------
1. John Franco (University of Cincinnati, Department of Electrical Engineering, Computer Engineering, and Computer Science)
   http://www.ececs.uc.edu/~franco/


참고문서(References)
--------------------------------------------------------
* 한국어(Korean)
저자. 역자. "제목". 출판사. 출판년도. (ISBN:)

* 영어(English)
저자. 제목, 판, 출판사. 출판년도. (ISBN:)
1. Wikipedia : Red-black tree
   http://en.wikipedia.org/wiki/Red_black_tree

2. Mathworld : Red-Black Tree
   http://mathworld.wolfram.com/Red-BlackTree.html

3. CS 660: Combinatorial Algorithms - Red-Black and B trees
   http://www.eli.sdsu.edu/courses/fall95/cs660/notes/RedBlackTree/RedBlack.html#RTFToC2