728x90 AVL 트리 개념과 특징 AVL 트리란? 이진 탐색 트리(BST)의 한 종류 스스로 균형(balancing)을 잡는 트리 balance factor(BF)를 통해 균형 유지 노드의 balance factor란? 임의의 노드 x에 대해서 BF(x) = h(lSubtree(x)) - h(rSubtree(x)) BF = balance factor, h = height, lSubtree = left subtree, rSubtree = right subtree AVL의 트리의 특징 balance factor가 -1, 0, 1 셋 중 하나의 값을 가짐. 트리에 삽입 혹은 삭제 후 BF(x)가 -1, 0, 1이 아니라면 노드가 생기면 균형을 맞추는 작업을 수행! AVL 동작 방식 🟨 오른쪽 오른쪽으로 편향된 상태 중간값을 위로 올림. (왼쪽.. 2022. 7. 25. 이전 1 다음 728x90