BS, Splay, AVL, BB

이진 탐색 트리(BS트리)

이진 탐색트리는 특정 데이터의 효과적인 검색을 위해 제한점을 가지는 이진트리를 말하고 특정  데이터의 검색과 노드의 삽입, 삭제 처리에 효과적이다. 트리를 구성할 때 데이터의 타색으로 고려하여 구성되므로 탐색에 최적화되어 있다. 이때 키값이라는 값이있는데 탐색, 삽입, 삭제 연산에서 비교 대상이 되는 값이다. 이진트리노드의 데이터를 대표하는 값이나 노드를 특정할 수 있는 값이 키이다.

이진 탐색 트리의 정의에는 노드 V_i의 키를 K_i라고 할때 각 노드 V_i가 2가지를 만족하는 이진트리이다.

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

이러한 이진트리를 중위순회하면 정렬된 순서 숫자가 작은 것부터 나열된다.

BS트리 노드정의
typedef struct BSTnode{
struct BSTnode* left;
char key;
char content [10];
struct BSTnode* right;
} BSTnode;


BS트리 중위순회
void inorderBST(BSTnode* root){
if(root!=NULL){
inorderBST(root
→left);
printf("% c", root
→key);
inorderBST(root
→right);
}}

 

BSTnode* searchBST(BSTnode* node, char key){
if(root == NULL){
printf("Error : 값을 찾을 수 없습니다.\n");
return root;
}
if(key == root → key){
return root;
} else if(key <root → key){
searchBST(root → left, key);
} esle if(key > root → key){
searchBST(root → right, key);
}}

 

1. 트리가 비어있다면 탐색 실패, 아니면 k와 현재루트노드의 키값 k_i를 비교한다.
2. k = k_i 이면 탐생성공으로 이때 찾은 정점은 v_i이다.
3. k < k_i이면 v_i의 왼쪽 서브트리를 탐색한다. v_i = vi, left로 바꾸고 1번으로 간다.
4. k > k_i이면 v_i의 오른쪽 서브트리를 탐색한다. v_i = vi, right로 바꾸고 1로 간다.

삽입연산

1. k = k이면 멈춘다.
2. k < k 이면 v의 왼쪽 서브트리에 삽입해야 하므로 v=v→left로 하고 4로 간다.
3. k > k 이면 v의 오른쪽 서브트리에 삽입해야하므로 v = v →right로 바꾸고 4로 간다.
4. 트리가 비어 있으면 키 k를 가지는 노드를 삽입한다. 그렇지 않으면 다시 k와 현재 루트노드의 키 k를 비교하여 탐색을 반복한다.

노드의 삭제

자식을 하나만 삭제하는 경우는 삭제한 노드를 가리키던 부모의 포인터가 그 노드의 NULL이 아닌 서브트리의 루트를 가리키게 할당한다.

두 개의 자식노드를 가지는 노드를 삭제할 때는 항상 특정 방향의 자식을 올려야 하는데 왼쪽노드에 있는 가장 큰 값을 올리면 오른쪽은 문제가 없다. 또는 오른쪽서브트리에서 가장 오른쪽에 있는 가장 작은애를 올린다.

 

Splay, AVL, BB트리

이진 탐색 트리의 특징은 트리의 구조와 특정노드에 접근할 확률은 BS트리의 성능에 영향을 준다. 트리의 성능이 구조에 영향을 받으며 어떤 노드의 탐색과 삽입, 삭제를 위해 접근 정보를 예측할 수 없는 상황에서는 최적의 BS트리를 결정하기 어렵다. 이때 경험적으로 좋은 성능의 BS트리를 구축하는 방법으로 자주 탐색하는 키를 가진 노드를 트리의 루트에 가깝게 놓는다는 것이다. 또는 트리가 균형이 되도록 유지하는 것으로 각 노드에 대해 왼쪽과 오른쪽 서브트리가 가능한 같은 수의 노드를 같게 하는 것이다.

 

Splay트리

자주 탐색하는 키를 가진 노드를 루트에 가깝게 위치하도록 구성하는 BS트리로 Splay연산은 최근 접근한 노드 X를 다시 사용할 것으로 예상하여 루트에 위치시켜 트리를 재구성하는 연산이다. 따라서 Splay트리는 최근에 사용한 노드가 트리의 루트에 올 때까지 Splay연산을 반복하여 생선 된 이진트리이다.

Splay트리의 연산
노드 x : 최근에 접근한 노드
노드 p : x의 부모노드
노드 g : x의 조부모 노드
zig : p가 트리의 루트면 p와 x의 간선연결을 회전시킨다.
zig-zig : p가 루트가 아니고 x와 p가 동일하게 왼쪽 자식들 또는 왼쪽, 오른쪽 자식들이면 p와 조부모 g와의 간선연결을 회전시키고 x와 p의 간선연결을 회전한다.
zig-zag : 만약 p가 루트가 아니고 x가 왼쪽자식 p가 오른쪽 자식이면 x와 p의 간선연결을 회전시키고 그다음 x와 x의 새로운 부모인 g와 간선 연결을 회전시킨다.

 

AVL 트리

노드의 삽입과 삭제가 일어날 때, 노드의 키값과 서브트리 키값 사이의 관계를 유지하면서 균형을 유지시키는 것은 쉽지 않다. 노드가 많으면 많은수록 균형을 유지하기 위해 너무 많은 움직임이 필요하다, 그리서 AVL트리의 개념은 제한 조건완화하여 완전한 균형이 아닌 것을 허용하며 무너진 균형의 정도는 작아야 하고 평균 탐색길이도 완전균형트리의 탐색길이와 크게 차이가 없어야 한다. 균형트리에 가까운 높이가 균형 잡힌 높이균형트리라고도 한다. 따라서 직접 탐색 성능이 매우 좋다

 

AVL의 조건은 노드 V의 왼쪽과 오른쪽의 서브트리높이가 1만큼 차이나야 한다.

 

BB트리

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

베타라는 균형을 제어하기 위한 인수가 있고 균형 베터(0 <베타 <1/2)라는 것은 임의 노드 x에 대해 x의 한쪽 서브트리에 x노드수의 비율이 베타와 1-베타 사이에 있도록 제어해 주는 것이다. 

배타가 1/4이면 한쪽 서브트리는 다른 쪽서브트리에 비해 3배 정도 노드를 만이 갖는 것이 허용되는 조건이다 1이 되게끔 하는 것이고 트리에서 무게는 트리에 속한 잎노드의 개수이다.

 

 

균형트리

ABL 또는 BB트리에 대해서 각 높이, 무게 제한조건을 만족시키는데 드는 비용은 트리를 완전히 균형 잡히게 유지하는 비용보다 훠린 짝다. 삽입이나 삭제를 완전히 균형잡히게 하려면 O(n)의 노드를 옮겨야 하지만 AVL, BB트리는 O(log₂ n) 개의 노드를 옮기면 되는 것으로 알려져 있다.