[자료구조] BST(Binary Search Tree) 이진 탐색 트리- C++

BST (Binary Search Tree)

이진 탐색 트리

• 특정 노드를 기준으로 왼쪽 서브트리에는 해당 노드보다 작은 값으로 이루어져 있고 오른쪽 서브트리는 해당 노드보다 큰 값으로 이루어져 있는 이진 트리(Binary Tree) 이다.

조건:

• 특정 노드 기준 왼쪽은 해당 노드보다 작은 값으로 이루어진다.
• 특정 노드 기준 오른쪽은 해당 노드보다 큰 값으로 이루어진다.

이진 트리(Binary Tree)

각 노드가 최대 2개의 자식을 가지는 트리 구조, 이진 트리에서 각 노드는 0~2개의 자식을 가질 수 있다.

이진 트리의 조건

• 각 노드가 0~2개의 자식 노드를 가진다. → 노드가 없는 빈 트리는 단순히 루트가 없는 상태로 정의되며, 이진 트리의 특성을 만족한다.
  
• 각 노드의 자식 노드는 왼쪽 자식과 오른쪽 자식으로 구분되고 두 자식이 이진 트리 이면 이진트리로 간주한다.

시간 복잡도

BST의 주요 연산은 삽입(Insertion), 삭제(Deletion), 검색(Search)으로

1. 삽입(Insertion):

• BST에 새로운 값을 삽입하는 과정은 트리의 적절한 위치를 찾아서 삽입하는 것이다.

• BST의 삽입은 새로운 값이 루트 노드에서 시작해 루트노드보다 크다면 오른쪽, 작다면 왼쪽으로 이동해 그 위치의 자식들과의 비교를 반복해 자리를 찾는다.

• 리프 노드에 추가되는 과정으로 값이 삽입될 때마다 트리의 구조를 유지해야 한다.

  → 따라서 삽입 연산은 트리의 높이에 비례하여 시간이 소요된다. 모든 자식이 0~2개의 자식을 가지기 때문에 트리가 균형적으로 생성된 경우는 평균적으로 O(log n)의 시간 복잡도를 가진다.
  

• 최악의 경우는 트리가 편향되어 있는 경우이며, 이 때의 시간 복잡도는 O(n)이다.
  (n은 트리의 노드 수)

2. 삭제(Deletion):

• BST에서 노드를 삭제하는 과정은 삭제할 노드의 자식 노드의 개수에 따라 경우를 나누어 처리해야 한다.

  1. 자식이 없을 때 : 해당 노드만 삭제
  2. 자식이 하나 있을 때 : 해당 노드를 삭제하고 자식을 원래 해당 노드 자리로 이동
  3. 자식이 두 개 있을 때 :
     • 왼쪽 subtree의 가장 큰 노드( 가장 오른쪽 노드) 나
     • 오른쪽 subtree의 가장 작은 노드( 가장 왼쪽 노드) 로 해당 노드를 삭제한 자리 대체

• 삭제 연산 역시 트리의 구조를 변경하므로, 삭제 후에도 BST의 조건을 유지해야 한다.

  → 트리가 균형적으로 생성되어 있는 경우에는 평균적으로 O(log n)의 시간 복잡도를 가진다.
  

• 최악의 경우는 트리가 편향되어 있는 경우이며, 이 때의 시간 복잡도는 O(n)이다.
  (n은 트리의 노드 수)

3. 검색(Search):

• BST에서 특정 값을 검색하는 연산은 트리를 탐색하는 과정으로 BST의 특성에 따라 값을 찾기 위해서는 트리를 순회하며 비교를 해야 한다.
• BST의 검색 연산은 트리의 높이에 비례하여 시간이 소요된다. 트리가 균형적으로 생성되어 있는 경우에는 평균적으로 O(log n)의 시간 복잡도를 가진다.
• 최악의 경우는 트리가 편향되어 있는 경우이며, 이 때의 시간 복잡도는 O(n)이다.
  (n은 트리의 노드 수)

따라서 BST의 시간 복잡도는 주로 트리의 높이에 의해 결정되며, 트리의 균형을 유지함으로써 평균적으로 O(log n)의 시간 복잡도를 가진다. 하지만 트리의 편향이 심할 경우 최악의 경우에는 O(n)의 시간 복잡도를 가진다.

🧀 BST의 높이가 logn인 이유

BST의 높이가 O(log n)이 되는 이유는 각 노드에서의 분기가 이진으로 이루어지기 때문이다.

BST에서는 각 노드의 왼쪽 자식은 현재 노드보다 작은 값이고, 오른쪽 자식은 현재 노드보다 큰 값이 된다. 이진 탐색 트리의 특성 상, 어떤 노드를 탐색하려 할 때마다 탐색 대상이 현재 노드의 왼쪽 서브트리 또는 오른쪽 서브트리 중 하나로 줄어들게 된다.

따라서 BST의 높이는 탐색할 노드를 선택할 때마다 대략적으로 높이가 절반씩 줄어들게 되어 O(log n)의 시간복잡도를 가진다.

🧀 BST의 worst case

BST의 worst case는 트리의 균형이 깨져 한쪽으로 치우친 상태로 트리 구조가 아닌 linked list 와 유사한 구조를 이룬다.해결을 위해서는 자가 균형 이진 탐색 트리 알고리즘으로 이진 트리의 균형이 잘 맞도록 유지해 높이를 가능한 낮게 유지한다.

EX : AVL트리, Red-black 트리

레드블랙 트리(BST 트리의 일종)

1. 모든 노드는 블랙이나 레드이다.

2. root와 leave(NIL)노드는 블랙이다.

3. 노드가 레드라면 부모 노드는 블랙이다.(연속해서 2대가 레드일 수 없다.)

4. 임의의 노드 x로 부터 모든 가능한 leave까지 거리는 항상 같다.

   → 리프 노드에서 루트 노드까지 가는 경로에서 만나는 블랙 노드의 갯수는 같다. (자기 자신은 제외하고 계산)

레드블랙 트리의 시간복잡도 : O(logn)

구현(C++)