#.7 BST

1. BST (Binary Search Tree) vs Tree

• Tree
  • 트리는 그 자체로는 데이터의 특성에 아무런 제약이 없음
  • 트리 구조는 특정한 값을 찾기 위해서 모든 값을 탐색해야함 (시간 복잡도 O(N))
• BST
  
  • 이진 탐색 트리는 이진 트리의 구조이지만, 데이터 값의 제약이 생긴다는 점에서 차이를 보인다.
  • 아래와 같은 제약을 줆으로써, 탐색 속도를 향상시켜준다. (시간 복잡도 O(logN))
  • 하나의 노드라도 아래의 조건을 충족하지 못하면 BST가 아님 
    • 노드의 왼쪽 하위 트리에는 노드의 키보다 작은 키가있는 노드 만 포함
    • 노드의 오른쪽 하위 트리에는 노드의 키보다 큰 키가있는 노드 만 포함
    • 왼쪽 및 오른쪽 하위 트리도 각각 이진 검색 트리
    • 중복된 키를 허용하지 않음

2. BST 연산

2.1 검색

• 전위탐색(preorder)를 한다면, BST의 규칙에 따라 검색하여 시간 복잡도가 O(logN)이 소요된다.

• BST는 중위 탐색(inorder)을 하면 크기 순으로 정렬된 탐색이 가능하다.

2.2 삽입

• BST는 중뽁된 데이터는 삽입되지 않는다.
• 데이터를 삽입할 시, 루트부터 값을 비교해가면서 트리를 타고 들어간다.
• 이를 통해서 BST의 조건을 유지하면서 삽입하게 되고, 항상 leaf 노드에 삽입된다.

2.3 삭제

• BST에서 데이터를 삭제할 때는, 위치에 따라 경우의 수가 3개가 된다.

1) 삭제할 데이터가 leaf인 경우

• 해당 노드를 삭제한다.

 

2) 삭제할 노드에 자식이 하나만 있는 경우

• leaf를 부모 노드로 보내준다.

3) 삭제할 노드에 자식이 둘이 있는 경우

• 해당 경우에는 2가지 옵션이 존재한다.
• 1) 왼쪽 서브 트리의 최대값과 교체
• 2) 오른쪽 서브 트리의 최소값과 교체