검색 트리

이진 검색 트리

1. 이진 검색 트리의 각 노드는 키값을 하나씩 갖고 키값은 모두 달라야 한다.
2. 루트 노드가 있고 각 노드는 최대 두 개의 자식을 갖는다.
3. 왼쪽 자식 노드의 키값보다 크고, 오른쪽 자식의 키값보다 작다.

-서브 트리

 

-이진 검색 트리 검색

1. 여기서 25을 찾으면 맨 처음 30보다 작아서 왼쪽, 20보단 커서 오른쪽으로 가면 25가 나온다.

2. 27을 찾으면 맨 처음 30보다 작아서 왼쪽, 20보다 커서 오른쪽 하지만 25보다 큰데 25의 자식이 없어서 27은 저 트리에 없다. 이러면 NIL이라고 한다.

 

-이진 검색 트리 삽입

-이진 탐색 트리 삭제

1. r이 리프 노드인 경우
2. r의 자식 노드가 하나인 경우
3. r의 자식 노드가 두 개인 경우

1. r이 리프 노드인 경우

그냥 삭제한다.

 

2. r의 자식 노드가 하나인 경우

30을 삭제하면 30을 삭제하고 그냥 붙여주면 된다.

 

3. r의 자식 노드가 두 개인 경우

여기서 28을 삭제하면 왼쪽 서브 트리와 오른쪽 서브 트리가 남는다. 그리고 여기서 두가지 케이스로 나뉜다.

1. 만약 왼쪽 서브 트리가 지금은 18 1개만 있지만 여러 개가 있으면 왼쪽 서브 트리 중에서 가장 큰 것을 삭제된 자리에 넣어준다.

2. 이 ppt에서는 오른쪽 서브 트리를 택했다. 오른쪽 서브 트리는 가장 작은 것을 삭제된 자리에 넣어준다. 따라서 가장 작은 30을 선택하고 삭제된 자리로 보내준다.

 

30을 보내고 나서는 남은 트리를 30이 었던 자리에 연결한다.

 

다른 예시

여기서 8을 삭제하면 왼쪽에서는 큰 값을, 오른쪽에서는 작은 값을 선택하는 것을 볼 수 있다.

 

AVL 트리

왼쪽 서트 트리의 높이 hL, 오른쪽 서브 트리의 높이 hR의 차이가 1 이하인 트리를 AVL 트리라고 한다.

노드의 균형 인수(BF) = hL - hR이며 균형 인수가 -1, 0, 1 값만 가져야한다.

 

루트 노드인 50은 hL이 2고 hR이 3이다. 따라서 BF는 2-3 = -1

 

-왼쪽

20은 hL이 1이고 hR이 0이라서 BF는 1-0 = 1

9는 hL, hR 모두 0이라서 BF 0

 

-오른쪽

55는 hL이 1, hR이 2라서 BF는 1-2 = -1

53은 hL, hR 모두 0이라서 BF 0

62는 hL, hR 모두 1이라서 BF 0

60, 65는 hL, hR 모두 0이라서 BF 0

 

-AVL 트리의 예

위에 숫자는 BF

 

-비AVL 트리의 예

a, b는 편향되어 있어서 그냥 꺾어주면 된다.

=> 단순 회전 LL, RR 같이 한 번 회전 하는 것

 

(a)

    20

9        50

 

(b)

     55

50       60

 

c, d는 가장 아래 노드를 중간에 끼고 a, b처럼 꺾으면 된다.

=> 이중 회전 LR, RL 같이 두 번 회전 하는 것

 

(c)

      50

20         55

 

(d)

      62

60         65

 

-AVL 트리 삽입

{50, 60, 70, 90, 80, 75, 73, 72, 78}이 순서 대로 삽입하면

최종적으로 이런 결과가 나온다. (꼭 종이에 해 보기)

 

-AVL 트리 삭제

여기서 50을 삭제하면 결과는?

 

답 1

 

 

답 2