�ݺ�ߣ

Balanced BST and AVL tree
이진 탐색 알고리즘을 이용한 균형 잡힌 이진 탐색 트리 구현
손고리즘2 알고리즘 기초 스터디
2015.09.21
발표자: 조 은 우

이진 탐색 트리 (Binary Search Trees, BST)
• 키(Key)-값(Value) 을 저장하기 위해 사용할 수 있는 자료 구조
• 이진 트리 (Binary tree)에 이진 탐색(Binary Search) 알고리즘을
사용해 키-값을 저장
• 왼쪽 노드(Left node)가 부모(Parent node)보다 작고, 오른쪽 노드
(Right node)가 부모보다 크다

이진 탐색 트리 구현
• 최초 추가되는 키(key)-값(value)을 루트 노드(Root node)로 저장
• 새로운 키-값이 추가되면 현재(or 루트) 노드와 비교
• 신규 키가 현재 노드 키보다 작으면 왼쪽 자식(Left node)으로 추가
• 신규 키가 현재 노드 키보다 크면 오른쪽 자식(Right node)으로 추가
• 해당 자식 노드에 이미 키-값이 있으면 다시 비교
• 키로 값을 찾는경우에도 루트 노드부터 비교하며 찾아감

트리 노드 구현
• 키(key), 값(value) 속성
• 부모 노드, 왼쪽 & 오른쪽 자식 노드를 저장
• 자신이 Leaf 노드인지 확인
• 왼쪽 자식 노드가 있는지 확인
• 오른쪽 자식노드가 있는지 확인
• 자신이 부모 노드에 대해 왼쪽 자식인지 확인
• 자신이 부모 노드에 대해 오른쪽 자식인지 확인

이진 검색 트리의 단점
트리 좌우의 균형이 맞지 않는 경우 트리 높이(Height)가 커짐에
따라 효율이 떨어짐
시간복잡도: O(n)

균형 잡힌 이진 탐색 트리
Balanced Binary Search Tr
ees
데이터가 삽입,삭제될 때 필요에 따라 스스로 균형을 유지
시간복잡도: O(log n)

AVL 트리
• 처음 논문을 통해 발표한 이들의 이름을 따서 지은 이름
• Balanced BST의 한 종류(외 2-3 BST, Red-Black BST)
• 트리 안에 모든 노드마다 왼쪽과 오른쪽 서브트리(sub tree)의 높이
(height) 차이에 대한 균형치(Balance factor)를 저장
• 균형치가 0보다 크면 Left-heavy 서브트리이며, 0보다 작으면
Right-heavy 서브 트리
• 노드가 삽입, 삭제될 때 회전(Rotation)을 통해 균형을 재구성

AVL 트리
균형치(Balance factor)

AVL 트리 구현
• 노드가 삽입, 삭제될 때 균형이 깨짐
• 삽입되는 신규 노드의 균형치(Balance factor)는 0 (zero)
• 삽입되는 위치에서 루트(root) 노드까지의 path에 있는 모든 부
모(parent) 노드들의 균형치에 영향을 줌
• 불균형 상태로 변한 노드 중 가장 가까운 부모 노드에 대해 균형
재조정(Rebalancing)

균형이 깨지는 경우
신규 삽입 노드를 N, 가장 가까운 불균형 상태 부모 노드를 A
• LL 타입: N이 A의 왼쪽(L) 서브트리의 왼쪽 자식으로 삽입
• LR 타입: N이 A의 왼쪽 서브트리의 오른쪽(R) 자식으로 삽입
• RR 타입: N이 A의 오른쪽 서브트리의 오른쪽 자식으로 삽입
• RL 타입: N이 A의 오른쪽 서브트리의 왼쪽 자식으로 삽입

균형 재조정 방법
신규 삽입 노드를 N, 가장 가까운 불균형 상태 부모 노드를 A
• LL 타입: A부터 N까지의 경로(Path)상의 노드들을 오른쪽 회전(Rotation)
• LR 타입: A부터 N까지의 경로(Path)상의 노드들을 왼쪽 - 오른쪽 회전
• RR 타입: A부터 N까지의 경로(Path)상의 노드들을 왼쪽 회전
• RL 타입: A부터 N까지의 경로(Path)상의 노드들을 오른쪽 - 왼쪽 회전

참고
http://interactivepython.org/runestone/static/pythonds/Trees/Objectives.html

�ݺ�ߣ

Balanced Binary Search Trees

More Related Content

Balanced Binary Search Trees