KalelPark's LAB

AVL tree란? - Binary SearchTree의 경우, 한쪽으로 노드가 쏠릴 수 있다. 트리에서 특정 값을 찾으려면 O(N)의 시간이 필요하다. 하지만, biasedTree를 AVL tree로 구성하면, 어떤 노드를 탐색하든 O(logN)에 탐색하는 것이 가능하다. - Binary Search Tree의 속성을 가집니다. - 왼쪽, 오른쪽 서브 트리의 높이 차이가 최대 1이다. - 높이 차이가 1보다 커지면 Rotation을 활용하여, 균형을 맞춰, 높이 차이를 최소화합니다. - 삽입, 검색, 삭제의 시간 복잡도가 O(logN) 이다. (N : 노드의 개수) Balance Factor(BF) - AVL트리는 균형이 무너졌는지에 대해 판단할 때, Balance Factor라는 것을 활용합니다. A..