728x90
AVL 트리
-
AVL 트리Computer Science/Data Structure 2021. 9. 24. 16:23
AVL 트리의 정의 ㆍ 균형 잡힌 높이의 이진 검색 트리이다. ㆍ 두 개의 자식 노드들 간에 깊이 차이가 1 이하인 트리이다. AVL 트리의 장점 ㆍ 트리의 검색 연산이 항상 O(log n)으로 균형 잡혀 있다. ㆍ 트리의 삭제 연산 또한 O(log n)으로 균형 잡혀 있다. AVL 트리의 단점 ㆍ 삽입 연산이 이루어질 때 트리의 재구성 시간이 소요된다. ㆍ 이진 검색 트리보다 구현의 난이도가 높다. 구현 방법 relink() 메서드 protected void relink(Node parent, Node child, boolean makeLeft) { if (child != null) child.parent = parent; if (makeLeft) parent.left = child; else pare..