비선형 자료구조 - 2. 이진 탐색 트리

이진 탐색 트리 (Binary Search Tree , BST)

 

이진 탐색 트리 , 출처 : https://ahribori.com/article/5948bf09b24df70e383033e8

 

이진 탐색 트리는 다음과 같은 규칙을 가진 이진 트리를 의미합니다.

 

• 모든 노드의 크기(or 값)가 왼쪽 자식 노드 < 부모 노드 < 오른쪽 자식 노드의 형태를 유지
  • 이로 인해, 각각의 서브트리는 이진 탐색 트리를 유지
• 중복된 값을 허용하지 않음

 

이진 탐색 트리 특징

 

데이터가 정렬되어 저장되어 이진 트리에 비해 탐색이 빠릅니다.

탐색의 시간복잡도는 균형 상태에서 O(logN) , 불균형 상태에서는 O(N)입니다.

빠른 탐색 속도를 위해, 이진 탐색 트리의 균형을 항상 유지하는 것이 중요합니다. 

 

이진 탐색 트리의 구조

탐색 (Search)

 

• 찾고자 하는 데이터를 root 노드부터 대소 비교
  
  • 데이터가 작으면 왼쪽 이동
  • 데이터가 크면 오른쪽 이동
• 찾는 데이터가 없으면 null 반환

 

삽입 (Insert)

 

• 균형 고려하지 않을 시
  • 삽입할 데이터를 root 노드부터 비교 (search와 동일)
  • leaf 노드에 도달 후, 작으면 왼쪽 , 크면 오른쪽에 삽입
  • 중복 키 발견 시 노드 추가하지 않고 종료

 

삭제 (Delete)

 

• 삭제 대상 노드가 Leaf인 경우
  • 삭제 대상 노드 삭제
  • 부모 노드의 해당 자식 링크 null로 변경
• 자식 노드가 하나 있는 경우
  • 자식 노드를 삭제 대상 노드의 부모노드에 연결
  • 삭제 대상 노드 삭제
• 자식 노드가 둘인 경우
  • 삭제 대상 노드의 왼쪽 서브 트리에서 가장 큰 노드 or 오른쪽 서브트리에서 가장 작은 노드 선택
    • 전자의 경우, 왼쪽으로 한 번 간뒤 오른쪽으로 쭉 내려가면 가장 큰 노드
    • 후자의 경우, 오른쪽으로 한 번 간뒤 왼쪽으로 쭉 내려가면 가장 작은 노드
  • 선택한 노드를 삭제 대상 노드의 위치로 올림
  • 올리면서 다른 자식 노드들의 링크 연결 작업
  • 삭제 대상 노드 삭제

 

균형 이진 탐색 트리

 

이진 탐색 트리에 데이터를 균형을 맞추지 않은 상태로 계속 추가하다보면, 편향된 이진 탐색 트리가 만들어지게 됩니다.

극한으로 편향될 경우, 탐색의 시간복잡도는 O(N)이 나오게 되므로 균형을 맞추는 것이 좋습니다.

 

균형 이진 트리는 이러한 균형을 맞춘 트리로 모든 노드의 좌우 서브 트리 높이가 1 이상 차이 나지 않는 트리를 의미합니다.

 

균형 이진 트리에는 대표적으로 AVL Tree, Red-Black Tree , Heap Tree 등이 있습니다.

 

AVL 트리

 

노드가 삽입 / 삭제될 때 트리의 균형을 체크하고 유지하는 트리입니다.

 

AVL Tree는 모든 노드에서 왼쪽 서브 트리와 오른쪽 서브 트리의 높이 차이가 1 이하로만 나야하며, 균형을 맞추기 위해 트리의 일부를 왼쪽 혹은 오른쪽으로 회전시킵니다.

 

💡 BF(Balance Factor)

왼쪽 서브 트리와 오른쪽 서브 트리의 높이 차리를 뜻하며, -1 , 0 , 1 의 값만 나와야 합니다.
만약, BF가 1보다 큰 값을 가진다면 왼쪽 서브 트리에 문제가, -1보다 작은 값을 가지면 오른쪽 서브 트리에 문제가 있는 것입니다.

 

회전 연산

 

AVL 트리는 노드가 삽입 / 삭제될 때 트리의 균형을 유지하기 위해 BF를 체크하여 다음과 같은 회전 연산을 합니다.

 

출처 :&nbsp;https://itwiki.kr/w/AVL_%ED%8A%B8%EB%A6%AC

 

 

Red-Black 트리

 

출처 :&nbsp;위키피디아

 

레드 블랙 트리는 노드에 색깔을 붙인 트리입니다.

 

구현은 복잡하지만, 실 사용에서 효율적이고 최악의 경우에도 우수한 실행 시간(O(logN))을 보장하기 때문에 많이 사용되고는 합니다.

 

다른 트리들과는 달리 자식이 하나도 없는 노드 끝에는 널 리프 노드(NIL)을 붙이며, 이는 단지 트리의 끝을 표현하는데에만 쓰입니다.

 

조건

 

다음 조건을 만족하여야 레드 블랙 트리라고 할 수 있습니다.

 

• 모든 노드의 색은 red 또는 black
  • root , leaf(NIL) 은 black
  • red 노드의 자식은 전부 black (red가 연속하여 등장할 수 없음, black은 가능)
• 모든 leaf 노드에서 root 까지 가능 경로의 black 노드 수는 동일

 

위의 조건이 깨지는 경우, 균형을 맞추어 주어야 합니다.

 

 

삽입

 

우선 레드 블랙 트리는 새로 삽입할 노드를 red로 추가합니다.

 

출처 :&nbsp;https://code-lab1.tistory.com/62

 

이때 빨간색 노드가 연속으로 등장하는 double red가 발생할 수 있습니다.

 

이를 해결하기 위해 레드 블랙 트리는 두가지 방법을 사용합니다.

 

출처 :&nbsp;https://code-lab1.tistory.com/62

• 부모 노드의 형제(삼촌 노드)가 red인 경우
  • Recoloring 진행
• 부모 노드의 형제가 없거나, black인 경우
  • Restructuring 진행

 

🎨 Recoloring 은 다음과 같은 과정을 거칩니다.

1. 삽입한 노드의 부모와 삼촌을 black 으로 변경
2. 조상 노드를 red로 변경
2-1. 조상 노드가 root라면 black으로 재변경
2-2. 조상 노드가 double red라면 Recoloring이나 Restructuring 진행

Recoloring 2-1

 

Recoloring 2-2

 

 

🔨 Restructuring은 다음과 같은 과정을 거칩니다.

1. 삽입한 노드, 부모 노드, 조상 노드를 오름차순으로 정렬
2. 정렬된 노드 중 가운데 노드를 부모 노드로 만들고 black으로 변경
3. 나머지 두 노드를 자식 노드로 만들고 red로 변경

Restructuring

 

삭제

 

삭제를 하는 경우 마주칠 수 있는 경우는 다음과 같습니다.

 

• 삭제 대상 노드가 black이고 그 자리에 오는게 red인 경우 (기본)

해당 자리로 오는 red를 black으로 변경

Case 1

 

• 삭제 대상 노드가 black이고, 그 자리에 오는 노드가 black인 경우 (Double Black Case)

Double Black Case 1. 삭제 노드의 형제가 black이며 형제 노드의 자식 노드가 모두 black

1. 형제 노드를 red로 변경
2. 이중 흑색 노드의 검은색 1개를 부모 노드로 전달
3. 부모가 root가 아닌 이중 흑색 노드라면 해당 과정을 반복 진행

 

Double Black Case 2.  이중 흑색 노드의 형제 노드가 red인 경우

1. 형제 노드를 black 변경
2. 부모 노드를 red 변경
3. 부모 노드 기준 왼쪽 회전
4. 이중 흑색 case에 따른 과정 반복

Double Black Case 3-1. 이중 흑색 노드의 형제 노드가 black이고, 오른쪽 자식이 red인 경우

1. 부모 노드와 형제 노드의 오른쪽 자식 노드를 검은색으로 변경
2. 부모 노드 기준 왼쪽 회전

 

Double Black Case 3-2. 이중 흑색 노드의 형제가 black, 왼쪽 자식이 red인 경우

1. 형제 노드를 red로 변경
2. 형제 노드 왼쪽 자식을 black으로 변경
3. 형제 노드 기준 오른쪽 회전
4. 이중 흑색 3-1 진행

 

 

AVL 트리 vs Red-Black 트리

 

공통점은 둘 다 O(logN)의 시간 복잡도를 가지고 있다는 점입니다.

 

차이점은 AVL 트리가 Red-Black 보다 좀 더 엄격하게 균형을 잡으며, Red-Black 트리는 색으로 구분하기 때문에 AVL 트리보다 회전 수가 적습니다.

 

보통 삽입,삭제가 많은 경우엔 Red-Black을, 탐색이 많은 경우엔 AVL 트리를 사용하는 것이 좋습니다.

 

 

 

 

프로그래밍 언어로 구현

Java

AVL Tree

public class AVLTree {

   Node head;

   public int height(Node node) {
      if (node == null) {
         return -1;
      }
      return node.height;
   }

   // LL Case
   public Node rightRotate(Node node) {
      Node lNode = node.left;

      node.left = lNode.right;

      lNode.right = node;

      node.height = Math.max(height(node.left), height(node.right)) + 1;
      lNode.height = Math.max(height(lNode.left), height(lNode.right)) + 1;

      return lNode;
   }

   // RR Case
   public Node leftRotate(Node node) {
      Node rNode = node.right;
      node.right = rNode.left;
      rNode.left = node;

      node.height = Math.max(height(node.left), height(node.right)) + 1;
      rNode.height = Math.max(height(rNode.left), height(rNode.right)) + 1;

      return rNode;
   }

   // LR Case
   public Node lrRotate(Node node) {
      node.left = leftRotate(node.left);

      return rightRotate(node);
   }

   // RL Case
   public Node rlRotate(Node node) {
      node.right = rightRotate(node.right);

      return leftRotate(node);
   }

   // BF 계산
   public int getBalance(Node node) {
      if (node == null) {
         return 0;
      }

      return height(node.left) - height(node.right);
   }


   // 노드 삽입
   public void insert(int key) {
      this.head = insert(this.head, key);
   }

   // 재귀로 노드 탐색 후, 삽입
   private Node insert(Node node,int key) {
      if (node == null) {
         return new Node(key, null, null);
      }

      if (key < node.key) {
         node.left = insert(node.left, key);

      } else {
         node.right = insert(node.right, key);
      }

      // 노드의 높이 업데이트
      node.height = Math.max(height(node.left), height(node.right)) + 1;

      // BF 체크
      int bf = getBalance(node);

      // 문제 있을 경우, 회전
      if (bf > 1 && key < node.left.key) {
         return rightRotate(node);
      }

      if (bf < -1 && key > node.right.key) {
         return leftRotate(node);
      }

      if (bf > 1 && key > node.left.key) {
         return lrRotate(node);
      }

      if (bf < -1 && key < node.right.key) {
         return rlRotate(node);
      }

      return node;
   }

   // 삭제
   public void delete(int key) {
      this.head = delete(this.head, key);
   }

   public Node delete(Node node, int key) {
      if (node == null) {
         return null;
      }

      if (key < node.key) {
         node.left = delete(node.left, key);
      } else if (key > node.key) {
         node.right = delete(node.right, key);
      } else {
         if (node.left == null) {
            return node.right;
         } else if (node.right == null) {
            return node.left;
         } else {
            Node pre = node;
            Node suc = node.left;

            while (suc.right != null) {
               pre = suc;
               suc = suc.right;
            }

            pre.right = suc.left;
            node.key = suc.key;
         }
      }

      node.height = Math.max(height(node.left), height(node.right)) + 1;

      int bf = getBalance(node);

      if (bf > 1 && getBalance(node.left) > 0) {
         return rightRotate(node);
      }

      if (bf < -1 && getBalance(node.right) < 0) {
         return leftRotate(node);
      }

      if (bf > 1 && getBalance(node.left) < 0) {
         return lrRotate(node);
      }

      if (bf < -1 && getBalance(node.right) > 0) {
         return rlRotate(node);
      }
      
      return node;
   }
   
   class Node {
      int key;
      int height;
      Node left;
      Node right;

      public Node(int key, Node left, Node right) {
         this.key = key;
         this.height = 0;
         this.left = left;
         this.right = right;
      }
      
   }

}

 

참고자료

https://code-lab1.tistory.com/62

제로베이스 백엔드 스쿨