💡 이진 탐색 트리 (Binary Search Tree)
👉 아래의 규칙으로 구성된 이진 트리
- 왼쪽 자식 노드의 키 < 부모 노드의 키 < 오른쪽 자식 노드의 키
- 각각의 서브 트리도 이진 탐색 트리를 유지한다.
- 중복된 키를 허용하지 않는다.
💡 이진 탐색 트리의 특징
👉 이진 탐색 트리 규칙에 의해 데이터가 정렬된다.
👉 이진 트리에 비해 탐색 속도가 빠르다. (But, 균형 유지 필요)
- 균형 상태에서의 속도 : O(logN)
- 불균형 상태에서의 속도 : O(N)
💡 이진 탐색 트리 - 탐색
👉 찾고자 하는 데이터를 루트 노드부터 비교한다.
👉 대소 비교를 하여 찾는 데이터가 작으면 왼쪽, 크면 오른쪽 노드로 이동한다.
👉 찾는 데이터가 없으면 null 을 반환한다.
👉 어떤 데이터를 찾더라도 최대 트리 높이 만큼의 탐색이 이루어진다.
💡 이진 탐색 트리 - 삽입
👉 루트 노드부터 대소 비교한다.
👉 중복 키 발견 시 노드를 추가하지 않고 종료한다.
👉 삽입할 키 < 현재 노드의 키 -> 왼쪽으로 이동
👉 삽입할 키 > 현재 노드의 키 -> 오른쪽으로 이동
👉 Leaf 노드에 도달 후 키 값을 비교하여 작으면 왼쪽, 크면 오른쪽에 삽입한다.
💡 이진 탐색 트리 - 삭제
👉 삭제 대상 노드가 Leaf 노드인 경우
- 삭제 대상 노드를 삭제한다.
- 부모 노드의 해당 자식 링크를 null 로 변경한다.
👉 삭제 대상 노드에 자식 노드가 하나인 경우
- 자식 노드를 삭제 대상 노드의 부모 노드에 연결한다.
- 삭제 대상 노드를 삭제한다.
👉 삭제 대상 노드에 자식 노드가 둘인 경우
- 두 가지 방법
1. 삭제 대상 노드의 왼쪽 서브 트리에서 가장 큰 노드를 선택하는 방법- 삭제 대상 노드의 오른쪽 서브 트리에서 가장 작은 노드를 선택하는 방법
- 1 or 2 에서 선택한 노드를 삭제 대상 노드 위치로 올린다.
- 위로 올리는 과정에서 다른 자식 노드들의 링크 연결 작업을 진을한다.
- 삭제 대상 노드를 삭제한다.
💡 균형 이진 트리
👉 모든 노드의 좌우 서브 트리 높이가 1 이상 차이 나지 않는 트리
💡 이진 탐색 트리의 편향 발생
👉 Case 1. 이진 탐색 트리에 삽입되는 순서 : 20 -> 10 -> 30 -> 5
👉 Case 2. 이진 탐색 트리에 삽입되는 순서 : 5 -> 10 -> 20 -> 30
💡 균형 이진 탐색 트리
👉 Balanced Binary Search Tree
👉 노드의 삽입과 삭제가 일어날 때 균형을 유지하도록 하는 트리
👉 종류 : AVL트리, Red-Black 트리
💡 AVL 트리
👉 노드가 삽입, 삭제될 때 트리의 균형을 체크하고 유지하는 트리
👉 각 노드의 BF를 -1, 0, 1 만 가지게 하여 균형을 유지한다.
👉 종류 : AVL트리, Red-Black 트리
BF (Balance Factor) = 왼쪽 서브 트리 높이 - 오른쪽 서브 트리 높이💡 AVL 트리 - 리밸런싱
👉 균형이 깨진 경우
- BF가 양수면 왼쪽 서브 트리에 이상이 있다.
- BF가 음수면 오른쪽 서브 트리에 이상이 있다.
👉 회전 연산을 통해 리밸런싱을 해준다.
- 단순 회전 : LL, RR
- 이중 회전 : LR, RL
👉 LL (Left-Left)
- 단순 회전으로 1회만 회전한다.
- 왼쪽 서브 트리에 이상이 있으므로 오른쪽 방향으로 회전하여 균형을 유지한다.
👉 RR (Right-Right)
- 단순 회전으로 1회만 회전한다.
- 오른쪽 서브 트리에 이상이 있으므로 왼쪽 방향으로 회전하여 균형을 유지한다.
👉 LR (Left-Right)
- 이중 회전으로 2회 회전한다.
- RR 회전 후 LL 회전하여 균형을 유지한다.
👉 RL (Right-Left)
- 이중 회전으로 2회 회전한다.
- LL 회전 후 RR 회전하여 균형을 유지한다.
💡 Red-Black 트리
👉 조건
- Root 노드와 Leaf 노드의 색은 Black
- Red 색 노드의 자식은 Black (Double Red 는 불가능하다.)
- 모든 Leaf 노드에서 Root 노드까지 가는 경로의 Black 노드 수는 같다.
👉 조건이 깨지는 상황에서 Rebalancing
💡 Red-Black 트리 - 삽입
👉 노드가 삽입 될 때는 Red 로 삽입된다.
👉 노드 삽입 후 Double Red 가 발생하는 경우
👉 Case 1. 부모 노드의 형제 노드가 Red 일 때
- Recoloring을 진행한다.
- 삽입한 노드의 부모와 부모의 형제 노드를 Black 으로 변경한다.
- 부모의 부모 노드를 Red 로 변경한다.
- 부모의 부모 노드가 Root 인지 Double Red 인지에 따라 조정을 진행한다.
👉 Case 2. 부모 노드의 형제 노드가 Black 이거나 없을 때
- Restructuring을 진행한다.
- 조정 대상 : 삽입한 노드, 부모 노드, 부모의 부모 노드
- 조정 대상 노드들을 오름차순으로 정렬한다.
- 가운데 노드를 부모 노드로 선정하고 Black 으로 변경한다.
- 나머지 두 노드를 자식 노드로 두고 Red 로 변경한다.
💡 Red-Black 트리 - 삭제
👉 Case 1. 기본 : 삭제 대상 노드가 Black 이고 그 자리에 오는 노드가 Red 인 경우
- 해당 자리로 오는 Red 노드를 Black 으로 변경한다.
👉 Case 2. Double Black Case : 삭제 대상 노드가 Black 이고, 그 자리에 오는 노드도 Black 인 경우
👉 Case 2-1. 이중 흑색 1 : 이중 흑색 노드의 형제 노드가 Black 이고, 형제의 양쪽 자식 모두 Black 인 경우
- 형제 노드를 Red 로 변경한다.
- 이중 흑색 노드의 검은색 1개를 부모 노드로 전달한다.
- 부모가 Root 가 아닌 이중 흑색 노드가 되면 해당 Case 를 반복한다.
👉 Case 2-2. 이중 흑색 2 : 이중 흑색 노드의 형제 노드가 Red 인 경우
- 형제 노드를 Black 으로 변경한다.
- 부모 노드를 Red 로 변경한다.
- 부모 노드를 기준으로 왼쪽으로 회전한다.
- 그 다음 이중 흑색 Case 에 따라 반복한다.
👉 Case 2-3. 이중 흑색 3-1 : 이중 흑색 노드의 형제 노드가 Black 이고, 오른쪽 자식이 Red 인 경우
- 부모 노드와 형제 노드의 오른쪽 자식 노드를 검은색으로 변경한다.
- 부모 노드를 기준으로 왼쪽으로 회전한다.
👉 Case 2-4. 이중 흑색 3-2 : 이중 흑색 노드의 형제 노드가 Black 이고, 왼쪽쪽 자식이 Red 인 경우
- 형제 노드를 Red 로 변경한다.
- 형제 노드의 왼쪽 자식 노드를 Black 으로 변경한다.
- 형제 노드를 기준으로 오른쪽으로 회전한다.
- 이중 흑색 3-1 Case를 진행한다.
💡 Red-Black 트리 VS AVL 트리
👉 알고리즘 시간 복잡도
- 모두 O(logN)
👉 균형 수준
- AVL 트리가 Red-Black 트리보다 좀 더 엄격하게 균형을 잡는다.
- Red-Black 트리는 색으로 구분하는 경우로 인해 회전 수가 감소한다.
👉 실제 사용 시, Tree 체계가 잡힌 후, 탐색이 많은 경우에는 AVL 트리가 유리하고, 삽입, 삭제가 빈번한 경우에는 Red-Black 트리가 더 유리하다.
BE