BST(이진 탐색 트리)

msung99·2022년 5월 8일
자료구조
0
post-thumbnail

BST

  • 모든 데이터가 internal 노드에 저장되는 이진트리

  • key 값(또는 entry) 를 저장. key를 이용해서 데이터를 구분

  • external 노드에는 key값(또는 entry) 를 저장하지 않음

  • inorder-traveral (중위순회) 가능.

    • 중위순회를 하면 오름차순으로 정렬된 순서가 출력된다.
    • 즉, BST를 중위순회하면 key값에 대해 오름차순으로 방문한다.

  • 동일한 item 들을 저장하고 있는 BST 는 여러가지 형태가 나올 수 있다.
    ex) 1,2,3 이라는 3개의 key값을 저장한 BST는 아래와 같은 다양한 형태가 나옴

형태1    형태2     형태3      형태4
  2       1           3     1
1   3       3       2         2
          2       1             3

구조 조건

  • 이진트리

순서조건

  • key(left_child) <= key(parent) <= key(right_child)
    • 왼쪽 자식의 key값은 parent 보다 작거나 같다
    • 오른쪽 자식의 key값은 parent 보다 크거나 같다

=> (모든 key값이 다르다고 가정)
특정 노드의 왼쪽 subtree : 해당 노드보다 작은 key들의 집합
특정 노드의 오른쪽 subtree : 해당 노드보다 큰 key들의 집합

Search (탐색 연산)

  • "왼쪽 서브트리는 해당 노드보다 작은 값, 오른쪽 서브트리는 해당 노드보다 큰 값" 이라는 특징을 활용

  • 임의의 key값을 주면, 그 key가 저장된 데이터를 찾을 수 있다.

  • 실행시간 : O(h)
    • 한 레벨을 내려가는데 비교연산을 1번 진행하므로, O(h) 이다!
    • 주의 : O(log n) 이 아니다!!!!!

탐색과정

  • 1) 탐색을 시작할 노드 v (일반적으로 root 노드) 와 탐색할 key인 k를 인자로 받는다.

  • 2) 찾으려는 값 k가 더 작으면 왼쪽 subtree 로 이동, 더 크면 오른쪽 subtree로 이동한다. (by 재귀호출)

=> 만약 k와 해당 노드의 key가 일치하면, 바로 리턴하면 끝!
=> k값을 갖는 노드 or external 노드를 만날떄까지 반복한다.

  • 3) external 노드에는 아무 값도 없으므로, 탐색을 실패하면 null 값을 갖는 external 노드를 리턴
Algorithm TreeSearch(k, v)
  if(v.isExternal())      // external 노드라면 null을 리턴하게 됨
    return v
  if k < v.key()                   // k의 값이 더 작은 경우, k는 왼쪽 서브트리에 존재
    return TreeSearch(k, v.left())
  else if k = v.key()             // k값이 일치하면 리턴하면 끝
    return v
  else if k > v.key()            // k의 값이 더 큰 경우, k는 오른쪽 서브트리에 존재
    return TreeSearch(k, v.right())

예시 : TreeSearch(4, root)

만약 TreeSearch(5, root) 를 호출한경우는?

  • 6 -> 2 -> 4 경로를 따라갔는데 5가 없고 external 노드를 만나게 된다. 즉, 5는 이 트리에 없다.

Insertion

  • put( k ) 메서드로 구현됨

  • 핵심은 삽입할 노드가 있어야 할 자리를 찾는 것이다.
    => TreeSearch() 를 활용

  • 원리
    => TreeSearch() 연산에서 탐색에 실패했을 때 external 노드가 리턴되는 것을 활용
    1) TreeSearch() 를 호출해서 정렬의 원리에 따라 external 노드에 도달한다.
    2) 리턴되는 external 노드 위치에 k값을 가지는 새로운 노드를 삽입한다.
    3) 삽입된 노드 왼쪽, 오른쪽 자식에 null 값을 가지는 external 노드를 양쪽에 매달아 줘서, 그 노드가 internal 노드가 되게한다.
  • 실행시간 : O(h)
  • 1) O(h)
    => TreeSearch() : 반드시 external 노드까지 내려가므로 수행시간은 트리의 높이 만큼이 걸린다.
    2) O(1)
    => key값으로 k가지는 새로운 노드 생성하고 트리에 매달고, 그 노드의 양쪽 자식에 null 노드 매다는 과정

예시 - put(5) => key 값 5를 삽입
삽입 전

삽입 후

Delection

  • erase( k ) 메서드로 구현된다.
  • 삭제하려는 CASE 는 3가지로 나뉜다
    1) 삭제할 노드의 왼쪽 or 오른쪽 자식 하나가 external
    2) 삭제할 노드의 왼쪽, 오른쪽 모두 external
    3) 삭제할 노드의 왼쪽, 오른쪽 모두 internal

삭제과정 요약

과정1) 삭제하려는 노드를 트리에서 탐색해서 찾아낸다
과정2)

case1) 삭제하려는 노드의 왼쪽or 오른쪽 자식이 external 인 경우

  • removeExternal() 로 같이 한 묶음으로 삭제
  • 삭제된 노드의 부모와, 삭제안된 나머지 한 자식을 이어준다.

case2) 삭제하려는 노드의 왼쪽, 오른쪽 자식이 모두 external 인 경우

  • removeExternal() 로 두 자식중 아무거나 한 묶음으로 같이 삭제
  • 삭제된 노드의 부모와, 삭제안된 나머지 한 자식을 이어준다.

case3) 삭제하려는 노드의 두 자식이 모두 internal인 경우

  • 삭제하려는 노드 k를 찾기(=탐색)
  • successor 찾기 (노드 k의 오른쪽 서브트리에 대해 중위순회를 진행)
  • 찾아낸 successor 값을 노드 k에 덮어씌우기
  • 기존의 successor 를 자신의 왼쪽 external 와 함께 삭제

삭제연산 종류

1) removeExternal(w) : 자식이 하나만 external 노드인 경우

  • 삭제하려는 노드와, 그의 자식 external 노드를 한 묶음으로 같이 삭제시킨다.
  • 삭제한 노드를 v 라하면, v.parent 와 v.child 를 서로 이어준다
    (이때 v.child 는 internal 노드로, 삭제안된 자식 노드)
  • 마치 링크드리스트 삭제연산과 유사

2) removeExternal(w) : 두 자식 모두 external 인 경우

  • 앞서 활용한 방법을 그대로 적용
  • 삭제하려는 노드와, 두 자식 중 아무 자식 external 노드를
    한 묶음으로 같이 삭제한다.
  • 그리고 삭제안된 나머지 한 자식 external 노드를 삭제한 노드의 parent와 이어줌

ex) 4를 삭제

3) 삭제하려는 노드의 두 자식 모두 internal 노드인 경우

실행시간 : O(h)
1) 삭제하려는 노드 찾기(=탐색) (즉, key값 k를 찾기) : O(h)
2) successor 찾기 : O(h) => 오른쪽 서브트리에 대해 external 이 나오기 직전노드를 찾기
3) 찾아낸 sccuessor 를 노드 k에 값을 덮어씌우기 : O(1)
4) 기존의 successor 를 자신의 왼쪽 external 과 함께 삭제 : O(1)
5) 삭제안된 나머지 한 자식을 삭제된 노드의 부모에 매달기 : O(1)

  • 힙처럼 삭제 대상 노드에 다른 노드를 덮어씌우는 방법을 사용

  • 과정1) 순서 조건을 지키기 위해, 대상 노드보다 큰 값중 가장 가까운 값(successor)으로 덮어씌운다.

    • 노드 k의 오른쪽 서브트리에 대해 중위순회를 한다면,
      첫번째로 visit되는 노드가 최솟값이다.
    • 즉, k의 오른쪽 서브트리에서 왼쪽으로 계속 파고 가다가 external 노드의 직전 노드가 successor 이다.

  • 과정2) removeExternal() 호출
    => successor을 대상 노드에 덮어씌우고 이후 successor와 그의 자식 external 노드(주로 left) 하나를 삭제한다.

    • successor의 왼쪽자식은 무조건 external 노드이다.
      (만일 sucessor의 왼쪽자식이 internal 이였다면, 그 자식 노드가 k 값과 더 가까운 노드 였을 것이다. 즉, successor가 최솟값이 아니다.)

예제) 노드 3을 삭제

  • successor 는 중위순회를 진행해보면 노드 5이다.
  • 5를 노드 3 자리에 덮어씌우고, 기존 sucessor와 그의 자식 external 노드를 삭제한다.

분석

BST

  • 사용공간 : O(n)
  • 탐색,삽입,삭제 연산 모두 : O(h)
    • worst case : O(n) ( = O(h) ) => 트리가 한쪽으로 쭉 나열된 형태인 경우
    • best case : O(log n) ( = O(h) ) => 균형이진탐색트리( 트리가 완전이진트리인 경우 )

  • n개의 아이템을 저장한 BST의 높이가 h라할때,

    • 공간 : O(n) 사용

최악의 경우 위 첫번쨰 그림처럼, BST가 쭉 나열된 형태일 수 있다.

  • 이 경우 h = n 이 된다.
  • 이렇게 생긴 BST의 경우 O(h) = O(n) 이므로,
    get, put, erase 3개의 연산 모두 O(h) 가 된다.
  • 몰론 best case으로 2번째 그림처럼 BST가 완전이진트리 형태가 된다면, 최악의 경우 O(log n) 가 된다.

=> Balanced Binary Search Tree(균형 이진탐색트리)

  • 높이가 O(log n) 인 BST 를 의미
  • 대표 예시 : AVL 트리
profile
msung99
이전 포스트

크롤링

다음 포스트

[JAVA] IO 스트림

0개의 댓글