• tree_insert(tree, key): key 추가
  • 구현하는 ADT가 multiset이므로 이미 같은 key의 값이 존재해도 하나 더 추가 합니다.

1) 새 노드 생성

• 새 노드를 동적으로 생성한다.
• 노드의 key를 입력받고, color를 RED로, 자식 노드들은 nil 노드로 설정한다.
• 이미 같은 key의 값이 존재해도 하나 더 추가 한다. (multiset)

2) 새 노드를 삽입할 위치 탐색

• 루트 노드부터 탐색을 시작하여 탐색 중인 노드보다 key값이 작은 경우 왼쪽 자식으로, 큰 경우 오른쪽 자식으로 이동한다.
• 탐색 중인 노드의 자식 노드가 nil 노드인 경우, 새 노드를 해당 자식 노드로 추가하고, 반복문을 종료한다.
• 반복문 종료 후 새 노드의 부모를 지정한다.

3) 불균형 조정

• 노드 삽입 후, 불균형을 해결해야한다.
• 새로 삽입된 노드는 항상 RED 색상으로 삽입되는데, 새로 삽입된 노드의 부모 노드가 RED인 경우, RB tree의 규칙을 위반하게 되어 불균형이 발생한다.
• 이 불균형을 해결하기 위해 총 3가지 CASE로 나누어 처리한다.

4) 회전

• 구조를 바꾸면서도 이진탐색트리의 특징을 유지시키는 방법은 회전이다.