JAVA 이진탐색트리 AVL 자료구조

- 전위순회

트리의 루트 노드 먼저 방문하고 왼쪽 서브트리를 순회한 뒤에 오른쪽 서브트리를 순회하는 방식

루트 - 왼쪽 서브트리 - 오른쪽 서브트리

 

- 중위순회

왼쪽 서브트리를 순회한 뒤 루트 노드를 방문하고 오른쪽 서브트리를 순회하는 방식

왼쪽 서브트리 - 루트 - 오른쪽 서브트리

 

- 후위순회

왼쪽 서브트리 - 오른쪽 서브트리 - 루트

---

전위 30 20 10 6 14 24 22 23 40 34 46

중위 6 10 14 20 22 23 24 30 34 40 46

후위 6 14 10 23 22 24 20 34 46 40 30

 

- 이진 탐색트리

최대 두개의 자식 노드를 가지는 이진 트리입니다. (왼쪽 서브트리, 오른쪽 서브트리)

 

정렬 조건

왼쪽 서브트리 < 현재노드 < 오른쪽 서브트리

중복된 값을 가진 노드는 허용되지 않습니다.

 

탐색과 정렬

특정 값을 효율적으로 탐색하고 정렬된 순서로 데이터를 저장하고 조회하는데 용이

균형이 잘 맞는 경우, 탐색, 삽입, 삭제 연산들이 평균적으로 O(log n) 시간에 이뤄집니다.

 

-삭제

단말 노드 삭제

(자식이 없는 노드)인 경우 해당 노드를 단순히 제거하면 됩니다.

 

자식이 하나인 노드 삭제

해당 노드를 삭제하고 자식 노드를 부모 노드와 연결하면 됩니다.

 

자식이 둘인 노드 삭제

삭제할 노드의 후속 노드 또는 전위 후속 노드와 값을 교환한 뒤 후속 노드를 삭제합니다.

---

- AVL tree

트리의 높이가 다를 경우 검색 효율이 떨어지므로 이를 조절하는 것이 균형트리입니다.

 

모든 node의 왼쪽과 오른족 서브트리 높이 차가 1을 넘지 않습니다.

트리의 높이를 변경하는 삽입, 삭제의 기본동작은 이진 탐색트리와 동일합니다.

기본 동작과 함게 트리의 균형을 재조정하는 추가 작업이 필요합니다.

 

장점 : O(log n)보장

단점 : 삽입과 삭제 시, 균형을 재조정하는 추가 연산이 필요(구현이 복잡함)

 

- 균형치

왼쪽 오른족 서브트리 높이 차가 1을 넘지 않으려면

왼쪽 (서브트리의 깊이 - 오른쪽 서브트리 길이) 값을 보관해야 합니다.

모든 최하위 node(leaf)의 균형치는 항상 0입니다.

이런 균형치를 맞출때 회전(Rotation)한다고 합니다.

 

- 사용 용도

대용량 데이터를 저장하고 관리하는 데이터베이스 시스템이나 파일 시스템에서 사용될 수 있습니다.

또한 실시간으로 데이터의 삽입과 삭제가 빈번하게 발생하는 상황,

그리고 데이터베이스 인덱스 구현이나 자동 완성 기능 등에서 활용됩니다.

 

- LL (Left Left)

왼쪽 자식 노드의 왼쪽 서브트리에 새로운 노드를 삽입할때 발생

왼쪽 자식의 왼쪽 서브트리의 높이가 더 큰 경우

이 경우에는 오른쪽 회전 (Right Rotation)을 통해 균형을 재조정 합니다.

 

- LR (Left Right)

왼쪽 자식 노드의 오른쪽 서브트리에 새로운 노드를 삽입할 때 발생

왼쪽 자식의 오른쪽 서브트리의 높이가 더 큰 경우

이 경우에는 왼쪽 자식을 기준으로 먼저 왼쪽 회전을 수행한 뒤, 오른쪽 회전을 통해 균형을 재조정 합니다.

 

- RR (Right Right)

오른쪽 자식 노드의 오른쪽 서브트리에 새로운 노드를 삽입할 때 발생

오른쪽 자식의 오른쪽 서브트리의 높이가 더 큰 경우

이 경우에는 왼쪽 회전을 통해 균형을 재조정 합니다.

 

- RL (Right Left)

오른쪽 자식 노드의 왼쪽 서브트리에 새로운 노드를 삽입 할 때 발생합니다.

오른쪽 자식의 왼쪽 서브트리가 높이가 더 큰경우

이 경우에는 오른쪽 회전을 수행한 뒤, 왼쪽 회전을 통해 균형을 재조정 합니다.