AVL Tree ratsgo's blog의 AVL Tree 를 참고하여 작성하였습니다. 이진탐색트리(Binary Search Tree)의 일종 이진탐색트리의 탐색 시간복잡도 : 𝑂(ℎ), h : 트리의 높이 서브트리의 높이를 조절해서 전체 트리가 한쪽으로 늘어지지 않도록 하는 것이 핵심 균형된 트리를 만들어 ℎ를 줄입니다. 기본적으로 삽입(insert) / 삭제(delete) 연산은 일반적인 BST과 동일합니다. 다만, 연산 이후 Balance Factor(BF) 값에 따라 서브트리를 재구성해 트리 전체의 균형을 맞춥니다 (Rebalance). Balance Factor(BF) : 왼쪽 서브트리의 높이에서 오른쪽 서브트리의 높이를 뺀 값 두 서브트리의 높이가 같거나 잎새노드라면 BF = 0 (em..

Binary Search Tree 이진탐색(binary search)과 연결리스트(linked list)를 결합한 자료구조입니다. 코드 전체를 보시려면 이곳 을 참고하세요. 이진탐색의 장단점 : 탐색 시간복잡도는 𝑂(log𝑛)으로 빠르지만 자료 입력, 삭제가 불가능 연결리스트의 장단점 : 자료 입력, 삭제 시간복잡도는 𝑂(1)로 효율적이지만 탐색은 𝑂(𝑛)의 시간복잡도가 소요되어 비효율적 이진탐색의 효율적인 탐색 능력을 유지하면서도, 빈번한 자료 입력과 삭제를 가능하게 만들어진 자료구조입니다. 특징 중복된 값을 가진 노드는 없습니다. 각 노드의 왼쪽 서브트리는 해당 노드의 값보다 작은 값을 지닌 노드들로만 이루어집니다. 각 노드의 오른쪽 서브트리는 해당 노드의 값보다 큰 값을 지닌 노드들로만 이루어집니다..