: Red Black트리라.. 저는 처음 알게 된 구조군요.
: AVL의 경우 Balance를 맞추기 위해 노드의 rotate가 들어가야하는데
: Red Black트리는 어떻게 다른지 궁금하군요.
:
: 저는 그냥 메모리 찍어보고 AVL트리와 유사한 구조, Node rotate가 이루어
: 지는 것을 보고 AVL이라고 생각하고 있었는데.. 음..
:
: 혹시 좀 자세히 아시면 한 수 가르쳐 주심이.. ^^
:
: 함 차자봐야게따..

찾아보면 많이 나옵니다.
웬만한 자료 구조책에 다 있지요.

보통 다음 순서대로 나오지요.

이진트리 -> AVL트리 -> B트리 -> 2-3트리 -> 2-3-4트리 -> Red-Black트리

2-3-4 트리를, 간선(edge)을 빨강과 검정의 색깔을 구분하여 이진 트리로 변환한 구조입니다.

다음은 몇 가지 링크입니다.

다음은 레드 블랙 트리가 AVL 트리보다 빠른 이유에 대한 글입니다.
http://kldp.org/script/bbs/read.php?table=qa2&no=2789&o[sc]=a&o[ss]=AVL&o[st]=a&o[at]=s&o[sct]=s&o[stt]=s

splay, Red-Black, AVL tree의 동작을 보여주는 자바 애플릿입니다.
http://www.seanet.com/users/arsen/avltree.html

GNU libavl 라이브러리입니다.
보통의 이진 트리, AVL 트리, Red-Black 트리를 모두 구현해 놓았죠.
리눅스에서는 커널을 비롯해서, 상당히 많이 사용됩니다.
임베디드 환경과 같이, ANSI C++을 쓸 수 없는 Only C 환경에서는 유용할 듯...
물론 STL보다는 엄청 저수준의 조작입니다.
http://www.msu.edu/user/pfaffben/avl/