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)로 효율적이지만 탐색은 𝑂(𝑛)의 시간복잡도가 소요되어 비효율적 이진탐색의 효율적인 탐색 능력을 유지하면서도, 빈번한 자료 입력과 삭제를 가능하게 만들어진 자료구조입니다. 특징 중복된 값을 가진 노드는 없습니다. 각 노드의 왼쪽 서브트리는 해당 노드의 값보다 작은 값을 지닌 노드들로만 이루어집니다. 각 노드의 오른쪽 서브트리는 해당 노드의 값보다 큰 값을 지닌 노드들로만 이루어집니다..

Sorting Algorithm Bubble Sort 서로 인접한 두 원소를 검사하여 순서에 맞지 않은 요소를 인접한 요소와 교환하며 정렬하는 알고리즘입니다. 선택 정렬 과 기본 개념이 유사합니다. 장점 구현이 매우 간단합니다. 단점 모든 케이스에 대해서 O(N^2) 입니다. 하나의 요소가 가장 왼쪽에서 가장 오른쪽으로 이동하는 경우 배열의 모든 다른 요소들과 교환되어야 합니다. 특히 특정 요소가 최종 정렬 위치에 이미 있는 경우라도 교환되는 일이 일어납니다. Pseudo code i = N-1 if i == 0, stop j=0 if j == i, go to 3. if array[j] > array[j+1], swap two values j += 1 and go to the 2-2 i -= 1 and ..

Tree 선형 구조가 아닌 계층 구조로 노드 와 노드를 연결하는 엣지 로 구성되어있는 자료구조입니다. 리스트, 스택, 큐 등의 선형 자료구조를 이용해서 조직도와 같은 계층구조를 구현하기란 쉽지 않죠. 계층형 구조를 담기 위한 자료구조 형태가 트리입니다. 용어 노드 : 데이터가 담기는 단위. 루트 : 부모가 없는 노드. 트리는 하나의 루트 노드만 존재. 리프 : 자식이 없는 말단 노드. 자식 : 하나의 노드 (부모 노드) 아래에 연결된 노드. 형제 : 같은 부모를 가지는 노드. 노드의 크기(size) : 자신을 포함한 모든 자손 노드의 개수. 노드의 깊이(depth) : 루트에서 어떤 노드에 도달하기 위해 거쳐야 하는 간선의 수 노드의 레벨(level) : 트리의 특정 깊이를 가지는 노드의 집합 노드의 차..