Tree Structure 노트8 - Red-Black Tree

Dynamic Operation을 위한 다양한 트리 자료구조가 있을 때, 사람들(coder)가 이해하기 좋은 구조와 사람에게는 어렵지만 컴퓨터에서 효율적으로 동작하는 구조 중 어느것이 좋은가?

Dynamic Tree Structure를 선택하는 기준 - Tree기반의 자료구조(Splay Tree, Min-max Tree, Split Tree, Leftist Tree..)/ 얼마나 많은 데이터를 처리해야 하는가?/ inserting이 자주 일어나는가 그리고 이 작업이 연속적인가?/ on-memory에서 효율적으로 동작하는가? 아니면 disk를 사용하는가?

 

Red-Black Tree는 복잡한 자료구조지만, 실사용에서 효율적이고, 최악의 경우에도 상당히 우수한 실행시간을 보임(worst-case guarantees). -> 실시간 처리와 같은 실행 시간이 중요한 경우에 유용하게 쓰임. +일정한 실행 시간을 보장하는 또 다른 자료구조를 만드는 데에도 쓸모있음./ 트리에 n개의 원소가 있을때 O(logN)의 시간복잡도로 삽입, 삭제, 검색 가능. (n개의 내부노드를 가지는 red-black tree는 높이가 O(logN))./ 비교 가능한 자료를 정리하는데 쓰이는 자료구조./ AVL 트리는 Red-Black Tree보다 더 엄격하게 균형잡혀있어서, 삽입 삭제시 최악의 경우 더 많은 회전(rotation) 필요./ Red-Black Tree는 함수형 프로그래밍에서 유용 -> 연관 배열(map, dictionary등)이나 집합(set)등을 내부적으로 Red-Black Tree로 구현해 놓은 경우가 많음. 

 

Red-Black Tree의 등장 - 2-3-4트리의 문제인 어떤 node는 degree가 2 어떤 것은 3 -> irregular함

이 2-3-4트리를 binary tree로 바꾸면 Red-Black Tree.

 

Red-Black Tree 규칙 : 모든 노드는 Red or Black/ root는 항상 black/ 노드가 Red이면, 그 노드의 자식들은 Black/ 모든 external leaf 노드들은 black/ Red노드의 자식노드 양쪽은 항상 모두 black(Red노드는 연달아 나타날수 없으며, Black노드만이 Red노드의 parent가 될 수있음)/ 루트에서 리프까지의 경로는 항상 같은 수의 Black 노드를 가져야 함.(이 제한조건이 전체의 깊이를 조절하는 중요한 factor이다)

 

중요 특성 : 루트 노드부터 가장 먼 leaf 노드 경로까지의 거리가, 가장 가까운 leaf 노드 경로까지의 거리의 2배보다 항상 작음. Red-black 트리는 roughly하게 균형이 잡혀있음. -> 삽입, 삭제, 검색시 최악의 경우에서의 시간복잡도가 트리의 높이에 따라 결정되기 때문에 보통의 Binary Search Tree에 비해 효율적임.

BST에서 worst 방지 - Height balanced tree(=self-organizing tree) ex) AVL Tree, 2-3 Tree, 2-3-4 Tree, b-Tree