[자료구조] 11. 이진 탐색 트리, Splay, AVL, BB

01. 이진 탐색 트리

 

✅ 이진 탐색 트리(binary search tree)

• 특정 데이터를 검색하고, 노드를 삽입/삭제하는 응용 문제에 가장 효과적인 이진 트리
• 탐색에 최적화된 이진 트리
• 키: 이진 트리 노드의 데이터(노드를 특정할 수 있는 값)

 

 

 

노드 Vᵢ의 키를 Kᵢ라 할 때 각 노드 Vᵢ가 다음을 만족하는 이진트리를 이진 탐색 트리(BS 트리)라고 함

1. Vᵢ의 왼쪽 서브트리에 있는 모든 노드의 키값은 Vᵢ의 키값보다 작다
2. Vᵢ의 오른쪽 서브트리에 있는 모든 노드의 키값은 Vᵢ의 키값보다 크다

 

 

같은 순서 데이터에 대해서 BS 트리를 다양하게 만들 수 있음

 

 

 

 

✅ BS 트리 순회

🔸BS 트리를 위한 노드 정의

 

 

 

🔸BS 트리의 중위 순회

 

 

 

🔸BS 트리의 노드 탐색

 BS 트리에서 키값이 K인 노드를 찾는 과정

① 트리가 비어있다면 탐색 실패, 비어있지 않다면 k와 현재 루트 노드의 키값 kᵢ를 비교한다.

② k = kᵢ 일 경우 탐색 성공, 이때 찾은 정점은 vᵢ 이다.

③ k < kᵢ 이면 vᵢ의 왼쪽 서브 트리를 탐색한다. 즉, vᵢ = vᵢ ,left로 바꾸고 ①로 간다.

④ k > kᵢ 이면 vᵢ의 오른쪽 서브 트리를 탐색한다. 즉, vᵢ = vᵢ ,right로 바꾸고 ①로 간다. 

 

 

 

🔸BS 트리의 노드 삽입 연산

BS 트리의 노드 삽입 연산

① 트리가 비어있다면 키 k를 가지는 노드를 삽입한다. 그렇지 않으면 k와 현재 루트 노드의 키 kᵢ를 비교한다.

② k = kᵢ 일 경우 멈춘다.

③ k < kᵢ 이면 vᵢ의 왼쪽 서브 트리에 삽입해야 하므로 vᵢ = vᵢ → left로 바꾸고 ①로 간다.

④ k > kᵢ 이면 vᵢ의 오른쪽 서브 트리에 삽입해야 하므로 vᵢ = vᵢ → right로 바꾸고 ①로 간다.

 

 

예)

키가 A인 노드와 F인 노드의 삽입

 

 

 

🔸BS 트리의 노드 삭제

노드 H 삭제

• 자식을 하나만 갖는 노드를 삭제하는 경우, [삭제한 노드를 가리키던 포인터]가 [그 노드의 null이 아닌 서브트리의 루트]를 가리키게 할당함
• 리프 노드의 경우 추가적인 작업 없이 바로 삭제 

 

• 두 개의 자식 노드를 가지는 노드는 삭제 시, 항상 특정 방향의 자식 노드를 올리는 방법으로 구현(항상 오른쪽(왼쪽) 자식 노드를 삭제 위치로 이동)
  • 특정 방향은 PM이 프로젝트 전에 미리 결정해둔대로 따름
• 구조를 가장 최소로 변화시키는 노드를 선택해서 삭제!

 

 

• 이진 트리 탐색을 사용하다 보니 탄생한 여러 트리들
  • splay 트리: 데이터 또는 키값을 찾을 때 예전에 찾았던 값을 또 찾는 경우가 생각보다 빈번하다는 입장에서 탐색 속도를 높이기 위해 만듬
  • BB 트리와 AVL 트리: 트리의 균형을 맞춤으로써 탐색의 속도를 높이려고 만듬

 

 

🔸이진 탐색 트리의 단점

• BS 트리의 성능은 트리의 구조와 특정 노드에 접근할 확률에 영향을 받음
• 트리의 성능이 구조에 영향을 받기 때문에 어떤 노드의 탐색/삽입/삭제를 위한 접근정보를 예측할 수 없는 상황에서는 최적의 BS 트리구조를 결정하기 어려움
• 휴리스틱 알고리즘(=경험적 알고리즘)을 사용하여 구축한 BS 트리의 성능이 최적에 가까움

 

 

🔸좋은 성능의 BS 트리를 구축하는 방법(휴리스틱)

1. 자주 탐색하는 키를 가진 노드를 트리의 루트에 가깝게 놓는다.
2. 트리가 균형(balance)이 되도록 유지한다. 즉, 각 노드에 대해 왼쪽과 오른쪽 서브트리가 가능한 같은 수의 노드를 갖게 한다.

 

 

 

 

 

 

 

02. Splay 트리

 

✅ Splay 트리

• 자주 탐색하는 키를 가진 노드를 루트에 가깝게 위치하도록 구성한 BS 트리
• Splay 연산: 최근에 접근한 노드 x를 (곧 사용할 것으로 예상하여) 루트에 위치시켜 트리를 재구성하는 연산
• Splay 트리: 가장 퇴근에 사용한 노드 x가 트리의 루트에 올 때까지 Splay 연산을 반복 적용하여 생성된 이진 트리

 

 

 

🔸Splay 트리의 연산

• 노드 x: 최근에 접근한 노드 
  노드 p: x의 부모 노드
• 노드 g: x의 조부모(부모의 부모) 노드

 

X의 키값 검색 확률이 높을 경우

① Zig: p가 트리의 루트면 p와 x의 간선 연결(edge joining)을 회전시킨다.

 

X의 키값 검색 확률이 높을 경우

② Zig-Zig: p가 루트가 아니고 x와 p가 동일하게 왼쪽 자식들 또는 오른족 자식들이면 p와 조부모 g와의 간선 연결을 회전시키고 그 다음에 x와 p의 간선 연결을 회전시킨다.

 

X의 키값 검색 확률이 높을 경우

③ Zig-Zag: 만약 p가 루트가 아니고 x가 왼쪽 자식, p가 오른쪽 자식(또는 그 반대)이면 x와 p의 간선 연결을 회전시키고 그 다음에 x와 x의 새로운 부모 p와의 간선 연결을 회전시킨다.

 

 

왼쪽 트리에 대해 7이 루트가 되도록 Splay연산을 적용

 

 

 

 

 

 

 

03. AVL 트리

 

✅ 변형 BS 트리 → AVL 트리

이진트리

 

노드 8 삽입(균형 유지됨)

 

노드 1 삽입(균형 깨짐)

균형을 위해서 많은 노드가 이동되어야 함

➡️ 노드의 삽입과 삭제가 일어날 때, 노드의 키값과 서브트리 키값 사이의 관계를 유지하면서 균형을 유지시키는 것이 쉽지 않음

 

 

🔸AVL 트리의 개념

• 제한 조건을 완화하여 트리가 (완전한) 균형이 아닌 것을 허용함
• 무너진 균형의 정도는 작아야 하고, 평균 탐색 길이도 완전 균형 트리의 탐색 길이와 크게 차이가 나지 않아야 함
• 거의 완전한 균형 트리의 한 형태로 높이가 균형 잡힌 높이 균형 트리(height balanced tree)
• 직접 탐색 성능이 매우 좋음

 

 

 

🔸AVL 트리의 조건

균형이 깨졌지만 허용

 

높이가 대략 균형잡힌 트리

 

노드 8이 제한 조건에 위배됨

• 노드 vᵢ의 왼쪽 서브트리 높이와 오른쪽 서브트리 높이가 최대 1만큼 차이가 남

 

 

 

 

 

 

 

04. BB 트리

 

✅ BB(bound-balanced)트리

• 거의 완전히(대략) 균형 잡힌 트리의 다른 종류로 무게가 균형 잡힌 트리
• 각 노드의 양쪽 서브트리 무게가 균형을 유지하는 트리

 

 

✅ 균형 트리

• AVL 또는 BB 트리에 대하여 각각 무게 또는 크기(높이) 제한 조건을 만족시키는데 드는 비용은 트리를 완전히 균형 잡히게 유지하는 비용이나 노력보다 훨씬 작음
• 십입이나 삭제 후에 트리를 완전히 균형합지게 유지하기 위해서는 O(n)의 노드를 옮겨야 하는 반면에 AVL 또는 BB트리는 O(log₂n)개의 노드를 옮기면 되는 것으로 알려져있음

➡️ 완벽한 균형이 아닌 적당히 허용된 균형(AVL, BB)이 여러모로 더 좋음