트리의 불균형을 해소하기 위한 방법 - AVL tree, Red_Black tree

트리의 불균형을 해소하기 위한 방법 - AVL tree, Red_Black tree

 

AVL tree는 Binary tree에 노드를 삽입하거나 삭제할 때마다 균형인수를 따져 불균형한 경우 노드를 재배치하는 알고리즘

 

균형인수(balance factor)

 

균형상태를 숫자로 나타낸 것

 

왼쪽 서브트리의 높이 - 오른쪽 서브트리의 높이