적흑트리 썸네일형 리스트형 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가지 특성이 모두 지켜진다.) 때문에 검은색인 경우.. 더보기 이전 1 다음
