[자료구조] Binary Search Tree 이진 탐색 트리

연산자

firstEntry() : 값이 null인 가장 작은 키 엔트리

lastEntry() 가장 키 값이 큰 엔트리

floorEnrty(k) 키 ≤ k 인 가장 큰 엔트리

ceilingEntry(k) 키 ≥ k 인 가장 작은 엔트리

• 맵이 비어있으면 null 리턴

Binary Search

• 이진 검색은 key로 정렬된 배열 기반 순차열로 구현된 정렬된 맵에서 get, floorEntry 및 ceilingEntry 연산을 수행
• 각 단계에서 후보 항목의 수가 절반으로 감소
• O(log n)

get floorEntry ceilingEntry O(log n)

put	O(n)
remove	O(n)

Binary Search Trees (ADT)

• 구조적 특성 : 이진 트리
• 관계적 특성
  • 내부 노드에 키(또는 키-값 항목)를 저장하는 이진 트리
  • u, v, w가 세 개의 노드라고 가정할 때, u는 v의 왼쪽 서브트리에 있고 w는 v의 오른쪽 서브트리에 있다. 이 경우, key(u) ≤ key(v) ≤ key(w)
  • 외부 노드는 항목을 저장하지 않는다.
  • 이진 검색 트리의 중위 순회(inorder traversal)는 키를 오름차순으로 방문

기본 메서드

get (k)

• 키 k와 같은 키를 가진 항목 (k, v)의 값을 반환
• 항목이 존재하면 해당 값을 반환

put (k, v)

• (k, v) 항목을 k를 v로 매핑하는 항목으로 입력

remove (k)

• 키가 k인 항목을 제거하고, 해당 항목의 값을 반환

Search - 키 k를 검색하기 위해 수행하는 방법

1. 루트에서 시작하여 하향 경로를 추적
2. 방문할 다음 노드
   • k가 현재 노드의 키보다 작으면 왼쪽 서브트리로 이동
   • k가 현재 노드의 키보다 크면 오른쪽 서브트리로 이동
3. 리프 노드에 도달
   • 리프 노드에 도달하면 키 k는 트리에 존재하지 않는다.

Algorithm TreeSearch(k, v)
if T.isExternal (v)
return v
if k < key(v)
return TreeSearch(k, T.left(v))
else if k = key(v)
return v
else { k > key(v) }
return TreeSearch(k, T.right(v))

삽입 (Insertion)

put(k, o)

1. 키 k를 검색(TreeSearch 사용)
   • TreeSearch(k)를 호출하여 키 k를 검색
   • 검색 경로를 따라 트리를 내려갑니다.
2. 키 k가 트리에 없음을 가정
   • 키 k가 이미 트리에 존재하지 않는다고 가정합니다.
   • 검색 결과 도달한 노드를 w라고 합니다.
3. 노드 w에 키 k 삽입
   • 노드 w에 키 k를 삽입하고 w를 내부 노드로 확장합니다.

예: 5 삽입

1. TreeSearch(5, root) 호출
   • 루트에서 시작하여 키 5를 찾기 위해 트리를 탐색합니다.
   • 키 5가 트리에 존재하지 않으면 리프 노드 w에 도달합니다.
2. 노드 w에 5 삽입
   • 리프 노드 w에 키 5를 삽입합니다.
   • 노드 w를 내부 노드로 확장하고, 필요한 경우 자식 노드를 추가합니다.

삽입 과정의 예시

1. 초기 상태
2. 10 / \\ 5 20 / \\ / \\ 3 7 15 25
3. TreeSearch(5, root) 호출
   • 키 5를 찾기 위해 루트에서 시작하여 트리를 탐색합니다.
   • 키 5는 이미 존재하므로 예를 들어 키 6을 삽입한다고 가정합니다.
4. TreeSearch(6, root) 호출
   • 루트에서 시작하여 키 6을 찾기 위해 트리를 탐색합니다.
   • 5 (왼쪽), 7 (오른쪽)으로 내려갑니다.
   • 리프 노드에 도달하고, 노드 w에 키 6을 삽입합니다.
5. 삽입 후 상태삭제 (Removal)
   1. 키 k를 검색합니다
      • 키 k를 검색하기 위해 트리를 탐색합니다 (TreeSearch(k) 호출).
      • 키 k가 트리에 존재한다고 가정합니다.
      • 키 k를 저장하고 있는 노드를 v라고 합니다.
   2. 노드 v가 리프 자식 노드 w를 가지고 있는 경우
      • 만약 노드 v가 리프 자식 노드 w를 가지고 있다면, v와 w를 트리에서 제거합니다.
      • 이 작업은 removeExternal(w) 연산을 사용하여 w와 그 부모 노드 v를 제거합니다.
   예: 4 제거
   1. TreeSearch(4, root) 호출
      • 키 4를 찾기 위해 루트에서 시작하여 트리를 탐색합니다.
      • 키 4를 저장하고 있는 노드를 v로 식별합니다.
   2. 노드 v의 리프 자식 w 확인
      • 노드 v가 리프 자식 노드 w를 가지고 있는지 확인합니다.
      • 리프 자식 w를 가지고 있다면, removeExternal(w) 연산을 수행합니다.
   삭제 과정의 예시

          10
         /  \\
        5    20
       / \\   / \\
      3   7 15  25
         /
        4
   

   1. TreeSearch(4, root) 호출
      • 루트에서 시작하여 키 4를 찾기 위해 트리를 탐색합니다.
      • 노드 7에서 왼쪽 자식으로 내려가 4를 찾습니다.
      • 노드 v = 7, 노드 w = 4로 식별합니다.
   2. 노드 v와 w 제거
      • 노드 v(7)와 노드 w(4)를 트리에서 제거합니다.
      • removeExternal(4) 연산을 수행하여 w와 그 부모 노드 v를 제거합니다.
   삭제 후 상태
6. 10 / \\ 5 20 / \\ / \\ 3 7 15 25
7. 초기 상태
8. remove(k)
9. 10 / \\ 5 20 / \\ / \\ 3 7 15 25 / 6

키 k가 삭제될 때, 자식 노드가 모두 내부 노드인 경우

1. 키 k를 저장하고 있는 노드를 찾습니다
   • 키 k를 검색하여 트리에서 노드 v를 찾습니다 (TreeSearch(k) 호출).
   • 노드 v의 자식 노드가 모두 내부 노드임을 확인합니다.
2. 중위 순회(inorder traversal)에서 v를 따르는 내부 노드 w를 찾습니다
   • v의 predecessor(이전) 또는 succesor(다음)
3. 노드 v에 key(w)를 복사합니다
4. 노드 w와 그 왼쪽 자식 z를 제거합니다
   • 노드 w와 그 왼쪽 자식 z(리프 노드)를 제거합니다.
   • removeExternal(z) 연산을 사용하여 z와 그 부모 노드 w를 제거합니다.

삭제 과정의 예시

초기 상태

       10
      /  \\
     5    20
    / \\   / \\
   3   7 15  25
      /
     4

1. TreeSearch(3, root) 호출
   • 루트에서 시작하여 키 3을 찾기 위해 트리를 탐색합니다.
   • 노드 v = 3으로 식별합니다.
2. 중위 순회에서 노드 v(3)를 따르는 내부 노드 w(4) 찾기
   • 중위 순회에서 노드 v(3)를 따르는 노드 w(4)를 찾습니다.
3. 노드 v(3)에 key(4) 복사
   • key(4)를 노드 v(3)에 복사합니다.
   • 이제 노드 v는 key(4)를 가집니다.
4. 노드 w(4)와 그 왼쪽 자식 z 제거
   • 노드 w(4)와 그 왼쪽 자식 z를 제거합니다.
   • removeExternal(z) 연산을 사용하여 z와 그 부모 노드 w를 제거합니다.

삭제 후 상태

       10
      /  \\
     5    20
    / \\   / \\
   4   7 15  25

성능

공간 복잡도	O(n)
get floorEntry ceilingEntry put remove	O(h) h: 트리의 높이
트리의 높이 h	O(n)