avl 트리
-
AVL 트리 구현 및 테스트프로그래밍 기초/알고리즘 2021. 9. 20. 17:45
AVL 트리 이진 검색 트리를 기반으로 노드에 Balance Factor(이후 BF)를 추가하여 BF의 상태에 따라 트리의 균형을 유지한다. ※ AVL 트리는 노드의 수가 n일 때 최대 깊이가 Ο(logn)이 되게 된다. AVL 트리의 개념 기본적으로 삽입과 삭제는 이진 검색 트리의 알고리즘을 그대로 따르며 이후 BF에 따라 보정하는 작업을 진행하여 트리의 균형을 유지한다. BF는 노드의 왼쪽 서브 트리의 깊이와 오른쪽 서브 트리의 깊이의 차이이다. 정상 상태일 때 BF의 범위는 [-1, 1]이 되게 되며 노드의 삽입 혹은 삭제를 통해 이 범위를 넘게 되면 균형이 무너진 것으로 판단한다. AVL 트리의 회전 알고리즘 BF가 무너진 노드를 x, x의 자식을 c, c의 자식을 c²라 하면 회전이 필요한 경우..