일단 룰이 빡쎄다!!...
레드블랙트리는 BST에서 균형이 깨지는 경우에 균형을 다시잡아주는 트리인데 룰이 빡쎄다... '문제점을 파악하고 어떠한 룰을 만들고 그 룰에대해 위반되는사항들에대해 조치방법을 만들어 놓은 것' 을 '레드블랙트리'라고 생각한다.
우선 먼저 개념을 익히고, 샘플코드를 살펴보고, 직접 코드작성에 들어갔을떄 NIL노드를 무시하고 그냥 NULL을 쓰다가 호되게 털렸다.
처음에는 위의 그림이 크게 와닿지 않았다. 하지만 실제 코드작성에들어가서 NIL노드 대신 NULL을 쓰다가 한번 털리고 다시 이그림을 보니 아!!.......
우선 NIL노드가 존재하는 이유 중 가장 큰 이유는 '형제노드'를 찾기 위함이다.
먼저 노드삭제과정에서 삭제된 노드가 블랙노드일경우 fixup(균형을맞춰주는 함수)을 호출하게되며, 삭제규칙에는 형제노드를 참조할수있어야 한다. 이때 fixup함수로 넘겨지는 노드는 삭제되는노드의 자식노드다(x라고 부르겠음). 이떄 x는 형제노드를 찾기위해 부모에 대한 링크를 가지고있어야한다. 근데 x가 NULL이라면?? 접근할 방법이 없다. 그래서 NIL노드가 필요하며, NIL노드는 일반노드와 동등하게 left,right,parent링크를 갖고 있을 것 이다.
다시 위의 그림을 보면, 모든 리프노드들과 루트노드의 부모도 NIL노드로 묶어준 것을 볼 수 있다. 여기서 중요하게 볼 포인트는, 다시 한번 말해 NIL노드는 하나로 '통합' 됬다는 점이다.
노드의 삽입과 삭제 과정에서 자식노드가 NIL노드인지 확인해야 할 때가 있다. 이때 NIL노드가 만약 각노드마다 개별 할당 되있다면 주소값이 틀릴 것이다. 하지만 위의 그림처럼 개별할당이아닌 하나의 노드로 다 연결시켜준다면 다음과같은 한 문장으로 NIL노드인지 아닌지 검사할수있게 되는 것이다.
if(node->left != nil) or if(node->right != nil) or if(node != nil) or if(node->parent != nil)
결론은 레드블랙트리에서 NULL은 포인터변수의 초기화값으로만 쓰이고 절대 다른곳에서는 사용되지 않는다.
삭제과정에서 대채노드를 왼쪽서브트리에서 가장 큰값을 취할지, 오른쪽서브트리에서 가장 작은값을 취할지 둘 중 아무거나 선택해도 상관은 없지만 실제삭제후에 두 트리의 구조를 비교해보면 서로 틀릴 때가 있다.
BST를 먼저 구현하고, fixup함수만 추가해준다고해서 레드블랙트리가 뚝딱 만들어 지는 것은 아니다.
일단 구조자체를 바꿔야한다. 예를들어, BST에서 parent멤버를 가지고있지않았다면 반드시 parent를 넣어줘야되고, dummy root노드도 없다면 추가해주고, nil노드도 만들어 줘야 한다,.
더미루트노드가 필요한 이유는, 삭제과정에서 부모노드와 자식노드를 요구할 때 가 있다. 그래서 실제 값이 들어있는 루트노드도 부모가 필요하므로 가상의 dummy root가 필요하다.
삽입과정에서 노드가 추가될때 항상 양방향(부모<->자식) 연결을 고려해야한다.
AVL vs RB
AVL은 균형을 빡세게 잡아주는 트리이며 반면, RB는 느슨하게 잡아준다. 그래서 성능차이를 배제하고 결과만 놓고 본다면 AVL이 균형을 더 잘잡아주기때문에 탐색이 더 빠를 수 있다.
하지만 성능상에서 보면, 흠. AVL과 RB에 대한 성능차에대해 의견을 다룬 여러 글을 봤는데 대채로 RB가 더 좋다고 한다. AVL은 최악의 경우 회전을 많이요구하지만, RB는 삽입과정에서는 최대2회 , 삭제과정에서도 많이 일어나지 않으며(3번을넘지않을것) 대채로 색깔바꿔주는 연산이 주로 일어나기떄문에 빠르다.
이 이슈에 대한 좋은 글을 퍼왔다.
| For small data: insert: RB tree & avl tree has constant number of max rotation but RB tree will be faster because on average RB tree use less rotation. lookup: AVL tree is faster, because AVL tree has less depth. delete: RB tree has constant number of max rotation but AVL tree can have O(log N) times of rotation as worst. and on average RB tree also has less number of rotation thus RB tree is faster. for large data: insert: AVL tree is faster. because you need to lookup for a particular node before insertion. as you have more data the time difference on looking up the particular node grows proportional to O(log N). but AVL tree & RB tree still only need constant number of rotation at the worst case. Thus the bottle neck will become the time you lookup for that particular node. lookup: AVL tree is faster. (same as in small data case) delete: AVL tree is faster on average, but in worst case RB tree is faster. because you also need to lookup for a very deep node to swap before removal (similar to the reason of insertion). on average both trees has constant number of rotation. but RB tree has a constant upper bound for rotation. |
출처 : https://stackoverflow.com/questions/16257761/difference-between-red-black-trees-and-avl-trees
공부하면서 참고했던 것 들
https://ko.wikipedia.org/wiki/%EB%A0%88%EB%93%9C-%EB%B8%94%EB%9E%99_%ED%8A%B8%EB%A6%AC
https://www.youtube.com/watch?v=gF20ZSplxZE&t=1349s
http://leeyongjeon.tistory.com/entry/C%EC%96%B8%EC%96%B4-%EB%A0%88%EB%93%9C%EB%B8%94%EB%9E%99-%ED%8A%B8%EB%A6%AC-%EC%82%AD%EC%A0%9C-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98RedBlack-Trees-in-C-deleting-or-removing-algorithm
http://egloos.zum.com/sweeper/v/900135 (샘플코드 다운받아볼 수 있습니다)
https://www.cs.usfca.edu/~galles/visualization/RedBlack.html (시뮬레이션인데 삭제과정에서는 왼쪽서브트리에서 가장높은값을 취함)
예제. (순서는 왼쪽에서 오른쪽으로)
원본트리에서 40을 삭제할 경우
