[비선형 자료구조]트리.그래프 (AVL 트리)

다룰것.

이진트리

최적 이진 탐색트리

AVL 트리

2-3 트리

2-3-4 트리

레드블랙 트리(rb트리)

M-원 트리

B-트리

etc

일반적인 이진트리이다. 그러나 마구잡이로 넣어버리면 한쪽방향으로만 뻗어가는 트리가 생길 수도 있겠지?

트리를 만드는 목적은 무엇이냐?

배열이나 단순한 링크드리스트같은 선형구조는 원하는 자료 탐색에 있어서 난항을 겪게된다.

여기에서 탐색을 위한 규칙성이 있다면 탐색하기 편하겠다. 그런데 이진트리에서 한쪽 방향으로만 뻗어버리면 배열과 다를게 없을것이다.

다음과 같은 이진탐색트리에서 알 수 있는 규칙성은?

한 노드에서 그 왼쪽으로 뻗은 자식은 부모보다 작은 숫자이다.

반면 오른쪽으로 뻗은 자식은 부모보다 큰 숫자이다.

트리는 탐색, 접근시간이 짧아야 한다. 여기서 AVL트리의 차례. 트리의 회전을 이용하자.

AVL Tree 개념 : http://blog.naver.com/ryutuna?Redirect=Log&logNo=100122795293

균형치(Balance Factor)가 +-2 미만이어야 한다. 2 이상일 경우 LL, RR, LR, RL 회전을 통하여 균형치를 맞춰준다.

LL회전

RR회전

LR회전

RL회전

용어 정리

1. 균형치(Balance factor)

- 균형치 = 왼쪽 서브트리의 높이 – 오른쪽 서브트리의 높이

2. 트리의 높이(Height)

- 높이 혹은 깊이(Depth)라고 하며 그 트리에 속한 노드의 최대 레벨로 정해진다.

3. 레벨(Level)

- 루트를 레벨1로 정의하기도 하고 0으로 정의하기도 하지만 본 문서에선 1로 정의하도록 하겠다. 만약 한 노드의 레벨이 L이라면 그 자식의 레벨은 L+1이 된다.

B+트리 설명은 다음 링크에서...

http://blog.naver.com/hytgogo?Redirect=Log&logNo=30121130366