[자료 구조] 스큐 트리 Skewed Tree

출처

ChatGPT

---

스큐 트리(Skewed Tree)는 한쪽으로 치우친 이진 트리를 말한다. 이 트리는 균형을 유지하지 못한 이진 트리로, 모든 노드가 왼쪽 또는 오른쪽으로만 연결되어 있다. 결과적으로 스큐 트리는 사실상 연결 리스트와 같은 구조가 되어 탐색, 삽입, 삭제와 같은 연산에서 비효율적일 수 있다.

 

스큐 트리의 종류

스큐 트리는 왼쪽 또는 오른쪽으로 치우칠 수 있다.

1. 왼쪽 스큐 트리 Left-Skewed Tree

모든 노드가 왼쪽 자식 노드만을 가지고, 오른쪽 자식 노드는 없는 트리이다.

 

예시

    5
   /
  4
 /
3

 

2. 오른쪽 스큐 트리 Right-Skewed Tree

모든 노드가 오른쪽 자식 노드만을 가지고, 왼쪽 자식 노드는 없는 트리이다.

  1
   \
    2
     \
      3
       \
        4
         \
          5

 

스큐 트리의 문제점

스큐 트리에서는 모든 노드가 한쪽 방향으로만 연결되어 있기 때문에, 이진 탐색 트리의 장점을 거의 잃게 된다. 이진 탐색 트리에서 탐색, 삽입, 삭제 연산의 시간 복잡도는 트리의 높이에 따라 결정되는데, 스큐 트리의 높이는 노드의 개수와 같아질 수 있다. 그 결과, 최악의 경우 시간 복잡도는 O(n)가 된다.

이것은 균형잡힌 이진 트리의 시간 복잡도 O(log n)에 비해 매우 비효율적이다.

 

스큐 트리가 발생하는 이유

스큐 트리는 데이터가 특정 순서로 삽입될 때 발생한다. 예를 들어, 이진 탐색 트리에 정렬된 데이터를 삽입할 경우, 트리는 한 쪽으로만 계속 자라서 스큐 트리가 된다.

 

예시

// 삽입 순서: 1, 2, 3, 4, 5
BinarySearchTree bst = new BinarySearchTree();
bst.insert(1);
bst.insert(2);
bst.insert(3);
bst.insert(4);
bst.insert(5);

 

위와 같이 오름차순으로 데이터를 삽입하면 트리가 오른쪽으로만 계속 자라며, 오른쪽 스큐 트리가 형성된다.

 

스큐 트리 해결 방법

스큐 트리는 자가 균형 이진 탐색 트리르 사용해 해결할 수 있다. 자가 균형 이진 탐색 트리는 트리의 삽입, 삭제 연산 후에도 트리의 균형을 유지하는 알고리즘을 사용해, 탐색, 삽입, 삭제 연산을 효율적으로 수행할 수 있다.

 

대표적인 자가 균형 이진 탐색 트리로는 AVL 트리와 레드-블랙 트리가 있다. 이들은 삽입 또는 삭제 시에 트리의 균형을 자동으로 맞춰주어, 트리의 높이를 log n으로 유지한다.

 

결론

스큐 트리는 한쪽으로 치우친 이진 트리로, 트리가 균형을 이루지 못해 탐색, 삽입, 삭제 연산에서 비효율성을 초래할 수 있따. 이러한 문제는 작가 균형 트리(레드-블랙 트리, AVL 트리 등)를 사용해 해결할 수 있다.