11-3. AVL트리, BB트리

03. AVL 트리

변형 BS트리 - AVL트리

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

 

AVL트리의 개념

- 제한 조건을 완화하여 트리가 (완전한)균형이 아닌 것을 허용함

- 무너진 균형의 정도는 작아야 하고, 평균 탐색 길이도 완전 균형 트리의 탐색 길이와 크게 차이가 나지 않아야 함

- 거의 완전한 균형 트리의 한 형태로 높이가 균형 잡힌 높이 균형 트리(height balanced tree)

- 직접 탐색 성능이 매우 좋음

AVL트리의 조건

AVL조건 : 노드 v_i의 왼쪽 서브트리서브 트리 높이와 오른쪽 서브 트리 높이 가 최대 1만큼 차이가 남

 

 

 

04. BB트리

BB트리의 정의

BB(bound-balanced)트리 : 거의 완전히(대략) 균형 잡힌 트리의 다른 종류로 무게가 균형 잡힌 트리

- 각 노드의 양쪽 서브 트리 무게가 균형을 유지하는 트리

- β는 균형을 제어하기 위한 인수

- 균형 β(0 <β≤1/2)라는 것은 임의의 노드 x에 대해 x의 한쪽(보통 왼쪽) 서브 트리에 x의 자식 노드 수의 비율이 β 와 1-β 사이에 있도록 제한하는 경우

- 만일 β = 1/2이면 왼쪽 서브 트리와 오른쪽 서브 트리는 같은 수의 노드를 가져야 함

     → 극단적으로 무게가 완전히 균형 잡힌 상태

- β = 1/4이면 한쪽 서브트리는 다른 쪽 서브 트리에 비해 3배 정도 노드를 많이 갖는 것이 허용되는 조건

- β가 1/2에 가까울수록 균형을 엄격하게 유지하게 됨

 

 

균형 트리

- AVL 또는 BB트리에 대하여 각각 무게 또는 크기(높이) 제한 조건을 만족시키는데 드는 비용은 트리를 완전히 균형 잡히게 유지하는 비용이나 노력보다 훨씬 작음

- 삽입이나 삭제 후에 트리를 완전히 균형 잡히게 유지하기 위해서는 O(n)의 노드를 옮겨야 하는 반면에 AVL 또는 BB트리는 O(log₂n) 개의 노드를 옮기면 되는 것으로 알려져 있음

 

 

 

11- 1, 2, 3 정리하기

- 트리에 특정 데이터가 있는지를 검색하고, 노드를 자주 삽입, 삭제하는 응용문제에 가장 효과적인 이진트리는 이진 탐색 트리(binary search tree)입니다.

- 키는 각 노드를 식별하기 위해서는 별도의 간단한 이름을 붙여준 것으로 노드의 데이터라고 생각할 수 있습니다.

- 이진 탐색 트리는 전위 순회, 중위 순회 및 후위 순회로 모든 정점을 차례로 순회할 수 있고 트리 내의 특정 정점을 탐색할 수도 있습니다.

- 이진 탐색 트리에서 새 노드는 항상 잎으로 삽입합니다. 즉, 루트부터 킷값을 비교하며 자기가 삽입될 위치가 왼쪽이냐 오른쪽이냐를 정하며 내려갑니다.

- Splay 트리는 자주 탐색하는 키를 가진 노드를 루트에 가깝게 위치하도록 구성한 이진 탐색 트리입니다.

- Splay 트리는 Splay 연산을 적용하여 최근에 사용하려고 접근한 노드 x를 루트에 위치시켜 트리를 재구성합니다.

- AVL 트리는 노드의 왼쪽 서브 트리 높이와 의 오른쪽 서브트리 높이가 최대 1만큼 차이가 난다는 조건을 만족하는 트리입니다.

- 트리의 높이란 노드가 가질 수 있는 가장 높은 레벨에 1을 더한 값으로 루트로부터 잎까지 가장 긴 경로 길이를 말합니다.

- 트리의 무게는 트리에 속한 잎 노드의 개수로 정의합니다.

- 무게가 균형 잡힌 트리란 각 노드의 양쪽 서브트리 무게가 균형을 유지하는 트리입니다. 이 트리를 무게가 균형 잡힌 트리(weight-balanced tree) 또는 BB-트리(bound-balanced)라고 부릅니다.

- AVL 또는 BB 트리에 대하여 각각 높이 또는 크기 제한 조건을 만족시키는데 드는 비용은 트리를 완전히 균형 잡히게 유지하는 비용이나 노력보다 훨씬 작습니다.

- 삽입이나 삭제 후에 트리를 완전히 균형 잡히게 유지하기 위해서는 O(n) 개의 노드를 옮겨야 하는 반면에 AVL 또는 BB 트리는 O(log₂n)개의 노드를 옮기면 되는 것으로 알려졌습니다.