이진탐색트리 - AVL 트리
AVL 트리AVL 트리는 이진탐색트리의 한 종류로편향된 트리구조가 나올 수 있는 이진탐색트리를 균형을 유지하도록 하여 시간복잡도가 평균 O(logN)을 유지하도록 한 트리이다. AVL 트리는 균형을 유지하기 위해 회전연산을 수행한다.LL 회전, RR 회전, LR 회전, RL 회전이라고 불리우는데, 회전 연산의 핵심 원리는 중간 값이 루트 노드가 된다는 것이다.LL, RR 등등은 노드의 왼쪽, 오른쪽 위치로 인해 붙여진 이름의 차이일 뿐,원리는 모두 할아버지, 부모, 자식이 있을 때, 중간 값이 루트가 되고 나머지 두 노드는 크기에 따라 왼쪽, 오른쪽에 위치하게 된다. BF(Balanced Factor, 균형인수)균형인수(BK) = 왼쪽 서브트리의 높이 - 오른쪽 서브트리의 높이균형인수는 AVL 트리가 트..
2025. 5. 30.
