레드 블랙 트리 (1) 썸네일형 리스트형 레드 블랙 트리 기존의 이진 검색 트리는 깊이가 원소 수 만큼 늘어날 수 있기 때문에 성능을 보장 받지 못한다는 단점이 있다. 그래서 이진 검색 트리에 몇 가지 제약을 걸어서 만든 것이 레드 블랙 트리이다. 레드 블랙 트리의 조건 1. 루트는 블랙 2. 리프는 블랙 3. 노드가 레드이면 자식은 블랙(no double red) 4. 루트에서 리프까지 만나는 블랙의 수가 일정하다. + 삽입된 노드는 레드 여기서 모든 리프가 블랙이라는 것은 우리가 생각하는 리프에 해당하는 말이 아니다. 위와 같이 자식이 하나이거나 없는 경우 NIL이라는 가상의 리프 노드를 붙여주고 블랙으로 만든다. 레드 블랙 트리는 이진 검색 트리에 이런 저런 조건을 건 것이므로 기본적으로 이진 검색 트리라고 할 수 있다. 즉 모든 삽입과 삭제는 이진 검색.. 이전 1 다음
