rbtree 썸네일형 리스트형 RB Tree 삽입 Red-Black Tree의 삽입 RB의 삽입에 대해 알아보자. 색 변환과 rotate를 제외하면 Binary Search Tree의 삽입과 같다. (BST를 이해하고 오자!) 위 그림과 같이 insert 하려는 node를 X, X의 부모를 P, 부모의 부모는 G, 부모의 형제인 삼촌노드는 U로 표현하자. 그리고 BST의 insert 과정이 끝났다고 생각하자. (즉, x가 어디에 위치할지 찾고 삽입한 것이다!) X는 항상 빨간색이다! X가 루트인 경우 X노드가 루트라면, RB의 특성 1을 유지하기 위해 BLACK으로 변경해준다. X가 루트가 아닌 경우 부모가 검은색인 경우 X는 항상 RED이므로 부모가 BLACK이면 삽입해도 RB가 깨지지 않는다!! (5가지 특성이 모두 지켜진다.) 때문에 검은색인 경우.. 더보기 RB Tree [레드 블랙 트리] https://ko.wikipedia.org/wiki/%EB%A0%88%EB%93%9C-%EB%B8%94%EB%9E%99_%ED%8A%B8%EB%A6%AC 레드-블랙 트리 - 위키백과, 우리 모두의 백과사전 레드-블랙 트리(Red-black tree)는 자가 균형 이진 탐색 트리(self-balancing binary search tree)로서, 대표적으로는 연관 배열 등을 구현하는 데 쓰이는 자료구조다. 1978년 레오 귀바스(Leo J. Guibas)와 로버트 ko.wikipedia.org Red-Black Tree Red-Black Tree(이하 rb)는 이진 트리의 한 종류이다. 그 중에서도 balanced search tree의 하나이다. rb는 자료의 삽입과 삭제, 검색에서 최악의 경우에도 O.. 더보기 이전 1 다음
