이진탐색트리
루트, 왼쪽서브트리, 오른쪽서브트리로 구성
루트 : 중간값
왼쪽서브트리 : 루트보다 작은값
오른쪽 서브트리 : 루트보다 큰값
주로 중위 순회를 함( 왼쪽 노드 오른쪽)
이유 - 오름차순으로 출력할 수 있기 때문
삽입 - 루트에서 시작해서 적절한 위치에 새노드 추가
삭제 - 1. 자식노드가 없는경우 : 그냥삭제
2. 자식노드가 하나인경우 : 삭제후 부모와 자식 연결
3. 자식노드가 두개인경우 : 오른쪽 서브트리에서 가장 작은값으로 대체
시간복잡도 (검색, 삽입, 삭제 다 같음)
평균 O(log n)
최악 O(n) ( 불균형 트리 일 때)
장점
- 평균적으로 O(log n ) 시간복잡도를 가짐
- 정렬된 데이터를 효율적으로 관리가능
- 중위순회를 통한 오름차순으로 출력가능
단점
- 불균형 트리 ( 한쪽으로 치우쳐질 수 있음) <- O(n)의 시간복잡도
- 균형상태를 유지하려면 AVL,레드블랙트리 필요
IPL(내부경로길이)구하는법
루트부터 1로 시작해서 층마다 1씩 더하면서 내려가서 다더하면됨
레드 블랙트리
레드 블랙 규칙을 사용하여 트리의 균형을 맞춤
규칙
- 각 노드는 레드 또는 블랙 색상이다.
- 루트 노드와 모든 리프노드는 검은색이다.
- 레드 노드의 자식은 무조건 검은색이다.
- 루트에서 임의의 리프노드까지의 검은색 노드의 수는 모두 동일하다
규칙이 있는 이유 : 높이를 제한하여 최악의 경우에도 O(log n)을 유지
장점
- 트리의 높이를 제한하여 탐색, 삽입, 삭제 연산 모두 O(log n)을 가짐
- 트리의 균형이 유지가 되기에 최악의 경우에도 효율적임
삽입
연속으로 두개 이상의 빨간색 노드가 안나오게, 검은색 높이가 알맞게 유지하면서 삽입 ( 안맞을 경우 색상변경 및 회전을 통해 균형을 맞춤)
삭제
삽입과 마찬가지로 색상하고, 검은색 높이를 알맞게 유지하면서 삭제해야됨
회전
좌측회전, 우측회전
좌측회전(LR) - 특정 노드가 오른쪽 자식으로 이동하고, 그 오른쪽 자식은 왼쪽 자식으로 이동
우측회전(RR) - 특정 노드가 왼쪽 자식으로 이동하고, 그 왼쪽 자식은 오른쪽 자식으로 이동
B-트리
각 노드가 여러 자식노드를 가질 수 있는 트리
검색, 삽입, 삭제 모두 O(log n)의 시간복잡도를 가짐
정해진 범위내에서 여러 자식을 가질 수 있음
노드의 구조
- 오름차순으로 정렬
- 노드는 최소 t-1개의 키를 가질 수 있고, 최대 2t-1개의 키를 가지 수 있음 (t=B트리의 차수)
- 각 노드는 최대 2t개의 자식을 가질 수 있음
모든 리프노드는 동일한 깊이에 위치 (균형트리)
노드 분할 및 병합
노드가 가득찰 시 분할이 발생하며, 중간 값이 부모 노드로 올라가게 됨
노드가 너무 적은 값을 가지게 되면 병합이 발생하여, 형제 노드와 합쳐짐
삽입
- 새로운 키를 삽입할 때, 적절한 리프노드를 찾아야함
- 노드가 가득 찰 시(2t-1개의 키를 가질 때), 분할을 수행후, 중간 값을 부모노드로 올립니다.
- 삽입은 항상 리프노드에서 이루어짐, 그 후 분할과 병합을 통해 높이 증가
삽입 과정
- 트리에서 적절한 리프 노드를 찾는다
- 노드가 가측 차 있으면 해당 노드를 분할
- 중간 값을 부모 노드로 올린다.
삭제
- 삭제는 검색을 먼저 수행하고, 그 노드가 리프 노드이면 바로 삭제하고, 그렇지 않으면 삭제할 노드를 대체할 키를 찾아 삭제합니다.
2.삭제 후에 리프 노드의 키가 부족하면 병합 또는 키 빌리기를 통해 트리의 균형을 맞춥니다.
3.병합 시에는 형제 노드와 합쳐지고, 부모 노드에서 해당 키가 삭제됩니다.
