2 - Binary-search-trees
Binary Search
- 정렬된 배열에서 특정한 값을 찾는 알고리즘
- 탐색 구간을 반으로 나누느 과정을 반복하여 동작. 탐색 키의 값이 중간 항목의 값보다 작으면 구간을 하위 반으로 좁히고, 그렇지 않으면 상위 반으로 좁힘.
- 리스트가 오름차순으로 정렬되어 있어야 올바르게 작동.
- 시간복잡도 : O(log₂n) 입력크기가 증가함에 따라 탐색 시간이 매우 느리게 증가
Binary Search Algorithm
- 정렬된 리스트의 중간값 선택 -> 탐색 키와 중간 값 비교 -> 리스트에 하나의 키만 남았고, 탐색 키와 일치하지 않으면 탐색 실패 -> 중간값보다 작으면 왼쪽 부분 리스트 , 중간값보다 크면 오른쪽 부분 리스트 확인
Binary Tree
- 각 노드가 최대 두 개의 자식 노드를 갖는 트리
Binary Search Tree (BST)
- 각 노드의 왼쪽 서브트리에는 해당 노드보다 작은 값들이, 오른쪽 서브트리에는 해당 노드보다 큰 값들이 위치하도록 정렬된 트리
- 특정한 순서로 정렬되어 있기 때문에, 시간 복잡도 O(log n)
- 각 노드는 고유한 키를 가진다, 우측 서브트리의 모든 노드의 키는 해당 노드의 키보다 작습니다. (좌측도 마찬가지)
Searching a Binary Search Tree
- 찾으려는 키와 루트 노드의 키를 비교 -> 찾으려는 키와 루트 노드의 키가 일치하면 성공 -> 찾으려는 키가 루트 노드의 키보다 작으면 왼쪽 서브트리를 탐색 or 루트 노드의 키보다 크면 오른쪽 서브트리 탐색 => 일치하는 키를 찾지 못했다면 실패.
Inserting into a Binary Tree
- 삽입하려는 키를 탐색 (이미 있는지 확인하기 위해서) -> 트리가 비어 있다면, 새로운 키를 삽입 하려는 위치에 맞게 왼쪽 또는 오른쪽 자식 노드로 연결
- 시간 복잡도 : O(n) or O(log n) 트리의 높이에 비례함
Deleting from a Binary Search Tree
- 삭제할 키를 탐색 -> 탐색에 성공시 -> 3가지의 case 중 하나
1) 자식이 없는 노드(leaf node)를 지울 때 : 연결된 링크를 끊고 해당 키를 가지고 있는 노드를 지워주면 된다. O(1)
2) 자식이 하나만 있는 노드(parent node)를 지울 때 : 하나의 자식을 위로 연결시켜준다 O(1)
3) 자식이 두개 다 있는 노드(parent node)를 지울 때 : 지우려는 node를 기준으로 오른쪽 자식중에서 가장 작은 값을 지우려는 node로 옮김 or 왼쪽 자식중에 가장 큰 값을 해당 자리로 옮김 O(log n)
Degenerate Binary Tree (퇴화 이진 트리)
- 모든 노드가 하나의 자식을 가지는 이진트리, 선형자료구조와 비슷
- 트리의 높이가 매우 커지는 문제, 노드를 추가 할 때 한 쪽으로만 자식 노드를 연결하는 경우
Full (Complete) Binary Tree (완전 이진 트리)
- 모든 레벨이 다 채워져 있고, 마지막 레벨의 노드들은 왼쪽부터 차례대로 채워져 있지 않을 수 있지만, 모든 노드가 최대한 왼쪽에 위치해야 함.
- 배열을 이용하여 효율적으로 저장가능
AVL Tree
- Height-Balanced Binary Search Tree는 완벽하게 balanced지 않다
- Balance Factor = Height(Left) - Height(Right) = -1,0,1 = 왼쪽 서브트리의 높이에서 오른쪽 서브트리의 높이를 빼준 값
AVL Tree Rotations
- balance factor의 값이 2 또는 -2가 되면, 트리의 균형이 무너지기 때문에 트리회전을 수행해야함
1) Single rotation (단일회전)
- Right rotation 또는 Left rotation
- 연속된 3개의 노드에서 수행
2) Double rotation (이중회전)
- Right-Left rotation 또는 Left-Right rotation
- 연속된 3개 또는 4개의 노드에서 수행
- LL : Single Right rotation 중간에 있는 node를 한번 돌린다
- RR : Single Left rotation
- RL : Left -> Right rotation
- LR : Right -> Left rotation
=> 책의 예시에는 LLRR는 반대로 회전하고 RL,LR는 이름 그대로 회전한다