이진 검색 트리

📌 이진 검색 트리

💡 이진 검색 트리(Binary Search Trees)

1. 히프의 문제점
   1. 임의의 데이터를 갖는 노드를 삭제할 경우의 시간 복잡도 : O(N)
   2. 트리에서 특정 데이터를 갖는 노드를 검색하는 시간 복잡도 : O(N)

2. 이진 검색 트리란?
   1. 트리 내에서 특정 데이터(Key 값) 을 갖는 노드를 효율적으로 검색
      - O(Log N), 하지만 정렬된 상태를 유지해야한다.

3. 이진 검색 트리의 정의
   1. 모든 노드는 유일한 키 값을 가지고 있다.
   2. 왼쪽 서브 트리에 저장된 키 값 < 루트 노드의 키 값
   3. 오른쪽 서브 트리에 저장된 키 값 > 루트 노드의 키 값
   4. 양쪽 서브 트리도 이진 검색 트리이다.

💡 검색 연산

1. 기본 개념
   1. if(key == root -> data) return
   2. if(key < root -> data) search(root -> left_child)
   3. if(key > root -> data) search(root -> right_child)
   4. 순환 알고리즘 혹은 반복문을 이용하여 구현한다.
      - 시간 복잡도는 O(트리의 Depth)

💡 이진 검색 트리에 노드 추가

1. 기본 개념
   1. 추가할 키 값이 이미 트리에 존재하는지 확인한다.
      - 트리의 유일성을 보장한다.
   2. 검색 알고리즘 수행 후, 알고리즘이 종료되는 곳에 새로운 노드를 추가한다.

2. modified_search(root, key)
   1. key 가 존재할 경우, return NULL
   2. 검색 알고리즘에서 방문한 마지막 노드에 대한 Pointer return
   3. 검색 성능은 O(Log N) 이 보장되는 것이 장점이다.

💡 이진 검색트리에서 노드 삭제

• 중위 순회를 이용하면, 오름차순으로 출력이 가능하다.

1. 리프 노드 삭제
   1. parent -> left_child = NULL

2. child 가 하나밖에 없는 노드의 삭제
   1. 삭제된 자리에 child node 를 위치하게 한다.

3. 두개의 children 을 갖는 노드를 삭제
   1. 왼쪽 서브트리에서 가장 큰 노드
      or
   2. 오른쪽 서브트리에서 가장 작은 노드를 삭제된 자리에 위치 시킨다.

💡 이진 검색 트리의 깊이

1. 데이터가 정렬된 순서로 입력 : O(N)
   - 1,2,3,4 : 편향 이진 트리
2. 데이터가 무작위 순서로 입력 : O(Log N)
3. 균형 이진 검색 트리 : AVL Tree, Red-Black Tree
   - 정렬된 데이터가 들어와도 O(Log N)을 보장한다.