탐색 트리

Binary Search Tree

각각의 노드가 BST 특성을 만족하는 키-주소 쌍을 가진 이진 트리

각 키에 대해,

왼쪽 서브트리의 모든 키는 이보다 작고,

오른쪽 서브트리의 모든 키는 이보다 크다.

모든 요소는 키를 가지고 있는데, 이 키는 유일하다.

만약, 이 BST를 중위순회(왼-루트-오)한다면 오름차순 방문하는 것. 

 

BST 검색(삽입)

검색 : 만일 BST가 공백이면 null 반환. 

삽입 : 만일 BST가 공백이면 단독 트리 만들고 true 반환

 

검색(삽입)하려는 key가 root.key보다 작으면 왼쪽 서브트리 순환 탐색, 

아니면 오른쪽 서브트리 순환 탐색

 

해서 검색이면 그 값을 찾고,

삽입이면 들어갈 자리를 찾음

 

검색 : 값 없으면 false 반환

삽입 : 이미 BST에 있는 키면 false 반환

 

* BST의 최솟값 검색 - x.left가 공백이 아닌 동안 x = x.left

 

BST 최선/최악

각 리프노드의 루트경로가 비슷하면 최선,

리프노드의 루트경로가 제각각이면 최악(특히, 리프노드 하나인데 트리 높이 긴 경우)

 

BST 삭제

삭제하는 경우는, 세 가지로 나눌 수 있다.

1. 자식이 없는 노드를 삭제하는 경우

 - 그냥 삭제하면 됨..

2. 자식이 1개인 노드를 삭제하는 경우

 - 자식을 삭제하려는 노드 자리로 올리면 됨..

3. 자식이 2개인 노드를 삭제하는 경우

 - 삭제하려는 노드의 중위 후속자를 찾아서 걔를 삭제하려는 노드 자리로 올리면 됨. 나머지 처리도 동일하게..

 

근데, 중위 후속자가 뭐냐?

x의 중위후속자 : x보다 큰 애들 중 가장 작은 애

x의 중위 후속자 구하기

 

이것도 세 가지의 경우가 있다.

if

1. x가 오른쪽 서브트리를 가지고 있는 경우

 - 오른쪽 서브트리 중 가장 왼쪽의 노드

else if

2. x가 오른쪽 조상을 가지고 있는 경우

 - 오른쪽 조상 중 가장 가까운 애

else

3. x가 트리에서 가장 오른쪽 원소인 경우

 - 얘가 젤 크기에 후속자 없음

 

AVL 트리 (Adelson-Velsky and Landis)

어떤 노드에서도 두 서브트리가 거의 같은 높이를 갖도록 강제로 균형을 유지하는 BST

불균형 발생하면 서브트리 회전해서 균형 맞춰줌

모든 노드에서 (왼쪽 서브트리 높이 - 오른쪽 서브트리 높이) 값이 -1, 0, 1 중 하나이면 AVL

 

- 피보나치 트리

AVL 특성을 만족하는 모든 이진 트리 중 최소 크기.

크기 범위 : 1.5^h <= n < 2^h

: 최악의 경우 AVL 트리가 되는데,

이를 생각하면 AVL 트리가 최악의 경우에도 로그 시간에 수행된다는 것을 알 수 있음.

 

public class AVLTree{
	private AVLTree(){
    	left = right = this;
        height = -1;
    }
    private AVLTree(int key, AVLTree left, AVLTree right){
    	this.key = key;
        this.left = left;
        this.right = right;
        height = 1 + Math.max(left.height, right.height);
    }
    
    private void ratateLeft(){
    	left = new AVLTree(key, left, right.left);
        key = right.key;
        right = right.right;
    }
    
    private void rotateRight(){
    	right = new AVLTree(key, left.right, right);
        key = left.key;
        left = left.left;
    }
}

 

 

 

 

출처 : 충남대학교 김경섭 교수님 수업자료