반응형 AVL트리1 [자료구조] AVL트리 AVL트리란 이진탐색 트리의 단점을 보완하고자 나온 트리이다. 이진탐색 트리의 큰 문제점은 한쪽 방향으로 노드가 쏠릴 수 있다는것이다. 저장하는 순서에 따라 발생되는문제인데 예를 들어 1, 2, 3, 4, 5, 6을 순서대로 저장한다고 하면 오른쪽 으로만 노드가 쏠려버리게되어 성능이 매우 나빠진다. AVL트리는 이런 이진트리의 단점을 보완이자 극복해준다. 특징 - 이진탐색 트리의 속성을 가진다. - 왼쪽, 오른쪽 서브 트리의 높이 차이가 최대 1이다. - 높이 차이가 1보다 커지면 회전을 통해 균형을 맞춰 높이 차이를 줄인다. - 삽입, 삭제, 검색의 시간복자잡도가 O(logn)이다. 상태 - LL상태 왼쪽 서브트리로 노드가 치우쳐있을때 사용하는 방식으로 오른쪽으로 회전하여 균형을 맞춘다. 순서 y노드의.. 2024. 1. 19. 이전 1 다음 반응형
