[자료구조] 이진 탐색 트리 / AVL 트리

이진 탐색 트리

이진 탐색 트리의 조건

• 각 노드에 값이 있다.
• 값들은 전순서가 있다.
• 노드의 왼쪽 서브트리에는 그 노드의 값보다 작은 값들을 지닌 노드들로 이루어져 있다.
• 노드의 오른쪽 서브트리에는 그 노드의 값과 같거나 큰 값들을 지닌 노드들로 이루어져 있다.
• 좌우 하위 트리는 각각이 다시 이진 탐색 트리여야 한다

※ 성능을 최대치로 끌어내기 위해서는 완전 이진트리에 가까워질 수 있도록 설계해야함

 

 

이진 탐색 트리 삽입 

• 삽입을 하기 전, 검색을 수행한다.
• 트리를 검색한 후 키와 일치하는 노드가 없으면 마지막 노드에서 키와 노드의 크기를 비교하여서 왼쪽이나 오른쪽에 새로운 노드를 삽입한다.

 

이진 탐색 트리 삭제

삭제하려는 노드의 자식 수에 따라

• 자식노드가 없는 노드(리프 노드) 삭제 : 해당 노드를 단순히 삭제한다.
• 자식노드가 1개인 노드 삭제 : 해당 노드를 삭제하고 그 위치에 해당 노드의 자식노드를 대입한다.
• 자식노드가 2개인 노드 삭제 : 삭제하고자 하는 노드의 값을 해당 노드의 왼쪽 서브트리에서 가장 큰값으로 대체하거나, 오른쪽 서브트리에서 가장 작은 값으로 대체한 뒤, 해당 노드(왼쪽서브트리에서 가장 큰 값을 가지는 노드 또는 오른쪽 서브트리에서 가장 작은 값을 가지는 노드)를 삭제한다.

 

AVL 트리

• 균형이 갖춰진 이진트리
• 간단한 구현과정으로 특정 이진트리가 완전 이진트리에 가까운 형태를 유지하도록 해줌
• 모든 노드에 대한 균형 인수가 1 또는 0인 트리를 의미
• AVL 트리에서 노드를 일반적인 이진 탐색 트리처럼 삽입, 삭제 시키면 높이 균형 성질을 만족하지 않으므로, 노드가 삽입, 삭제될 때 회전(rotation)을 통해 트리를 재구성하여 높이 균형 성질을 유지
  
  • 균형잡기는 노드가 삽입될 때마다 수행되어야함.
  • 삽입과정의 시간 복잡도는 O(logN)
  • 균형잡기는 삽입시 거치는 모든 노드에 대해 수행되므로 O(1) 시간복잡도를 만족해야함

 

균형인수(Balance Factor) 개념

균형인수 = 왼쪽 자식 높이 - 오른쪽 자식 높이 

균형인수가 2이상 인지에 따라 균형을 맞춤 → 회전을 통해 트리를 재구성

계산을 위해 항상 높이(height)값을 가지고 있음

 

 

균형이 깨지는 4가지 형식

1. LL형식 : X의 왼쪽 자식의 왼쪽에 삽입하는경우
2. LR형식 : X의 왼쪽 자식의 오른쪽에 삽입하는경우
3. RR형식 : X의 오른쪽 자식의 오른쪽에 삽입하는경우
4. RL형식 : X의 오른쪽 자식의 왼쪽에 삽입하는경우

 

AVL 트리 삽입

• AVL 트리 T에 새로운 노드 d가 단말 노드(leaf node)로 삽입될 수 있도록 하는 노드 w를 찾고 w의 자식으로 d를 삽입
• d를 삽입하면 불균형해질 수 있는데 세 노드를 기준으로 회전(rotation)시킴으로써 균형을 맞춤

 

AVL 트리 삭제

• Root부터 d를 검색하는데 d가 단말노드가 아니면 왼쪽 부분 트리중에서 최댓값을 갖는 노드나 오른쪽 부분 트리중에서 최솟값을 갖는 노드 d와 바꿈 → d가 단말 노드가 될 때까지 반복하여 d를 삭제함
• d를 삭제하면 불균형해질 수 있는데 삽입과 동일한 방법으로 d의 부모를 w라고 한뒤 회전시켜 균형을 맞춤

 

 

 

 

 

참고 | Wikipedia, Fast campus 컴퓨터 공학 전공 필수