제 5 장 탐색트리.

Presentation on theme: "제 5 장 탐색트리."— Presentation transcript:

1 제 5 장 탐색트리

2 탐색트리 저장된 데이터에 대해 탐색, 삽입, 삭제, 갱신 등의 연산을 수행할 수 있는 자료구조
저장된 데이터에 대해 탐색, 삽입, 삭제, 갱신 등의 연산을 수행할 수 있는 자료구조 배열이나 연결리스트는 각 연산을 수행하는데 O(N) 시간이 소요 스택이나 큐는 특정 작업에 적합한 자료구조. 5장에서는 리스트 자료구조의 수행시간을 향상시키기 위한 트리 형태의 다양한 사전 자료구조들을 소개 - 이진탐색트리, AVL트리, 2-3트리, 레드블랙트리, B-트리

3 5.1 이진탐색트리 이진탐색트리(Binary Search Tree): 이진탐색:
정렬된 데이터의 중간에 위치한 항목을 기준으로 데이터를 두 부분으로 나누어 가며 특정 항목을 찾는 탐색방법

4 이진탐색으로 66을 찾는 과정

5 트리 형태의 자료구조에서 이진탐색을 수행하기 위해 1차원 배열을 단순연결리스트로 만든 후, 점진적으로 이진트리 형태로 변환해가는 과정

6

7 이진탐색트리의 특징 중의 하나는 트리를 중위순회(Inorder Traversal)하면 정렬되어 출력

8 [정의] 이진탐색트리는 이진트리로서 각 노드가 다음과 같은 조건을 만족한다.
각 노드 n의 키값이 n의 왼쪽 서브트리에 있는 노드들의 키값들보다 크고, n의 오른쪽 서브트리에 있는 노드들의 키값들보다 작다. 이를 이진탐색트리 조건이라 한다. 어느 트리가 이진탐색트리인가?

9 5.1.1 이진탐색트리 클래스 노드(Node) 클래스는 이진트리의 구현에 사용된 노드와 거의 유사
노드 객체는 id(키), name(키에 관련된 정보), 왼쪽 자식과 오른쪽 자식을 각각 가리키기 위한 left와 right 필드를 가짐

10

11 Line 01: Key와 Value는 generic 타입이고, Key는 비교 연산을 위해 자바의 Comparable 인터페이스를 상속받음
키를 비교할 때 Comparable에 선언되어 있는 compareTo() 메소드를 사용하여 비교 연산을 수행 Line 05∼09: Node 클래스의 생성자 Line 11∼18: Node클래스의 get, set 메소드들

12 이진탐색트리를 위한 BST 클래스 Line 01: Key와 Value에 대한 부분은 Node 클래스와 동일
Line 03: root를 리턴하는 getRoot() 메소드 Line 04∼06: BST 클래스의 생성자 이진탐색트리의 기본 연산에 대한 메소드들 선언

13 5.1.2 탐색 연산 탐색하고자 하는 Key가 k라면, 루트노드의 id와 k를 비교하는 것으로 탐색을 시작
id가 k 보다 작은 경우, 루트의 왼쪽 서브트리에서 k를 찾고, id가 k 보다 큰 경우에는 루트의 오른쪽 서브트리에서 k를 찾으며, id가 k와 같으면 탐색에 성공한 것이므로 해당 노드의 Value, 즉, name을 리턴 왼쪽이나 오른쪽 서브트리에서 k를 탐색하는 연산은 루트노드에서의 탐색 연산과 동일

14 get() 메소드는 오버로딩(overloading)으로 2단계로 구현
Line 01: get() 메소드는 1 개의 매개변수인 Key k만을 인자로 갖고 Line 02: get() 메소드는 root와 k를 인자로 가짐 Line 03: 노드 n이 null인 경우 null을 리턴(탐색 실패) Line 04: k와 노드의 id, 즉, n.getKey()를 비교한 결과에 따라서 line 05 나 06에서 get()을 재귀호출하거나 line 07에서 k를 가진 노드를 리턴

15 [예제] 40을 탐색하는 과정

16 5.1.3 삽입 연산 삽입은 탐색 연산과 거의 동일 탐색 연산의 마지막에서 null이 반환되어야 할 상황에서 null을 반환하는 대신, 삽입하고자 하는 값을 갖는 새로운 노드를 생성하고 이 노드를 부모노드와 연결하면 삽입 연산이 완료 단, 이미 트리에 존재하는 id를 삽입한 경우, name을 갱신

17 Line 01: 두 개의 매개변수 Key k와 Value v를 가지며, line 02의 put() 메소드를 호출
[주의] line 01에서 root가 put() 메소드가 리턴하는 Node를 가리게 하는 것 Line 05, 06: setLeft()나 setRight()를 호출하여 put() 메소드가 리턴하는 Node를 연결

18 [예제] 35를 삽입하는 과정

19 35를 삽입할 장소를 탐색하는 과정

20 새 노드 삽입 후 루트노드로 거슬러 올라가며 재 연결하는 과정

21 5.1.4 최솟값 찾기 최솟값은 루트노드로부터 왼쪽 자식노드를 따라 내려가며, null을 만났을 때 null 의 부모노드가 가진 id min() 메소드는 delete() 메소드에서 사용

22 Line 01: min() 메소드와 line 05의min() 메소드로 구성
Line 05: min() 메소드는 인자로 전달받은 노드가 null이 아닌 한 계속 왼쪽 자식을 인자로 넘겨 min 메소드를 재귀호출하며(line 07), 왼쪽 자식이 null이면 왼쪽 자식이 null인 노드(최솟값을 가진 노드)의 레퍼런스를 리턴(line 06). Line 03: 리턴된 레퍼런스의 getKey()로 가져온 id를 최솟값으로 리턴

23 [예제]

24 5.1.5 최솟값 삭제 연산 최솟값을 가진 노드를 삭제하는 것은 최솟값을 가진 노드 x를 찾아낸 뒤, x의 부모노드 p와 x의 오른쪽 자식노드 c를 연결 이 때 c 가 null이더라도 자식으로 연결 deleteMin() 메소드는 임의의 id를 가진 노드를 삭제하는 delete() 메소드에서 사용

25 만일 트리가 empty라면 에러 메시지를 출력하고(line 02), 트리가 empty가 아닌 경우, line 04의 deleteMin() 메소드를 root를 인자로 하여 line 03에서 호출 이후 루트노드로부터 왼쪽 자식으로 계속 내려가다가(line 06), 왼쪽 자식이 null이면 현재 노드의 오른쪽 자식의 레퍼런스를 리턴 (line 05). 그 후부터는 루트노드까지 거슬러 올라가며 부모와 자식을 line 06에서 다시 연결

26 [예제]

27 5.1.6 삭제 연산 우선 삭제하고자 하는 노드를 찾은 후 이진탐색트리 조건을 만족하도록 삭제된 노드의 부모노드와 자식노드들을 연결해 주어야 삭제되는 노드가 자식이 없는 경우(case 0), 자식이 하나인 경우(case 1), 자식이 둘인 경우(case 2)로 나누어 delete연산을 수행 case case 1 case 2

28 Case 0: 삭제해야 할 노드 x의 부모노드가 x를 가리키던 레퍼런스를 null로 만든다.
Case 1: x가 한쪽 자식인 c만 가지고 있다면, x의 부모노드와 x의 자식노드 c를 직접 연결 Case 2: x의 부모노드는 하나인데 x의 자식노드가 둘이므로 x의 자리에 중위순회하면서 x를 방문하기 직전 노드(Inorder Predecessor, 중위 선행자) 또는 직후에 방문되는 노드(Inorder Successor, 중위 후속자)를 이동

29 delete() 메소드에서 삭제할 노드를 탐색하는 과정은 line 05∼06에서 재귀적으로 수행
Line 08: 삭제되는 노드의 오른쪽 자식이 null인 경우를 처리하는데, - case 0: 두 자식 모두가 null이므로 line 08의 조건에 해당 - case 1: 자식이 왼쪽 또는 오른쪽 둘 중에 한 개만 있으므로 오른쪽 자식이 없는 경우 역시 line 08의 조건에 해당 case 1에서 왼쪽 자식이 없는 경우는 line 09에서 처리

30 Case 2의 경우 삭제될 노드의 자리로 옮겨올 노드 n의 중위 후속자를min() 메소드를 호출하여 찾음(line 11).
Line 12: deleteMin() 메소드를 호출하여 노드 n을 트리에서 분리시키고, n의 부모와 n의 자식을 연결시킨 뒤, 계속해서 재 연결하며 거슬러 올라가며 최종적으로 삭제되는노드(target)의 오른쪽 자식노드의 레퍼런스를 리턴 리턴된 레퍼런스는 n.setRight()에 의해 n의 오른쪽 자식으로 연결 (line 12). Line 13: target의 왼쪽 자식을n.setLeft()를 이용해 노드n의 왼쪽 자식으로 만든다.

31 [예제 1] delete(10)이 수행되는 과정 (case 0)

32 [예제 2] delete(45)가 수행되는 과정 (case 1, line 08)

33 [예제 3] delete(35)가 수행되는 과정 (case 1, line 09)

34 [예제 4] delete(20)이 수행되는 과정 (case 2)

35 수행시간 이진탐색트리에서 탐색, 삽입, 삭제 연산은 공통적으로 루트노드에서 탐색을 시작하여 최악의 경우에 이파리노드까지 내려가고, 삽입과 삭제 연산은 다시 루트노드까지 거슬러 올라가야 함 트리를 1 층 내려갈 때는 재귀호출이 발생하고, 1 층을 올라갈 때는 setLeft() 또는 setRight() 메소드가 수행되는데, 이들 각각은 O(1) 시간 소요 연산들의 수행시간은 각각 트리의 높이(h)에 비례, O(h)

36 N개의 노드가 있는 이진탐색트리의 높이가 가장 낮은 경우는 완전이진트리 형태일 때이고, 가장 높은 경우는 편향이진트리
따라서 이진트리의 높이 h는 아래와 같이 표현 log (N+1)  log N ≤ h ≤ N Empty 이진탐색트리에 랜덤하게 선택된 N개의 키를 삽입한다고 가정했을 때, 트리의 높이는 약 1.39 log N

37 5.2 AVL트리 AVL 트리는 트리가 한쪽으로 치우쳐 자라나는 현상을 방지하여 트리 높이의 균형(Balance)을 유지하는 이진탐색트리 균형(Balanced) 이진트리를 만들면 N개의 노드를 가진 트리의 높이가 O(logN)이 되어 탐색, 삽입, 삭제 연산의 수행시간이 O(logN)으로 보장 [핵심 아이디어] AVL트리는 삽입이나 삭제로 인해 균형이 깨지면 회전 연산을 통해 트리의 균형을 유지한다.

38 [정의] AVL트리는 임의의 노드 x에 대해 x의 왼쪽 서브트리의 높이와 오른쪽 서브트리의 높이 차이가 1을 넘지 않는 이진탐색트리이다.
(a) (b) (c) 어느 트리가 AVL트리 형태를 갖추고 있나?

39 [정리] N개의 노드를 가진 AVL트리의 높이는 O(logN)이다.
[증명] A(h)를 높이가 h인 AVL트리를 구성하는 최소의 노드 수로 정의하자. 그러면 다음 그림에서 확인할 수 있듯이 A(1) = 1, A(2) = 2, A(3) = 4이다.

40 A(3)을 재귀적으로 표현해보면 A(3)이 위와 같이 구성되는 이유:
높이가 3인 AVL트리에는 루트노드와 루트의 왼쪽 서브트리와 오른쪽 서브트리가 존재해야 하고, 각 서브트리 역시 최소 노드 수를 가진 AVL트리여야 하기 때문 또한 이 두 개의 서브트리의 높이 차이가 1일 때 전체 트리의 노드 수가 최소가 되기 때문

41 A(h) = A(h-1) + A(h-2) + 1, 단, A(0)=0, A(1)=1, A(2)=2
A(h)와 피보나치 수 F(h)와의 관계 A(h) = F(h+2) – 1

42 피보나치 수 F(h)  h/5,  = (1+5)/2이므로,
A(h)  h+2/5–1 A(h)는 높이가 h인 AVL트리에 있는 최소 노드 수이므로, 노드 수가 N인 임의의 AVL트리의 최대 높이를 A(h) ≤ N의 관계에서 다음과 같이 계산할 수 있다. A(h)  h+2/5 – 1 ≤ N h+2 ≤ 5 (N + 1) h ≤ log(5(N+1)) – 2  1.44logN = O(logN). 

43 5.2.1 AVL트리의 회전연산 AVL트리에서 삽입 또는 삭제 연산을 수행할 때 트리의 균형을 유지하기 위해 LL-회전, RR-회전, LR-회전, RL- 회전연산 사용 회전연산은 2 개의 기본적인 연산으로 구현 rotateRight(): 왼쪽 방향의 서브트리가 높아서 불균형이 발생할 때 서브트리를 오른쪽 방향으로 회전하기 위한 메소드 rotateRight(): 노드 n의 왼쪽 자식노드 x를 노드 n의 자리로 옮기고, 노드 n을 노드 x의 오른쪽 자식노드로 만들며, 이 과정에서 서브트리 T2가 노드 n의 왼쪽 서브트리로 이동

44 (a) 수행 전 (b) 회전 후 [그림 5-21] rotateRight

45 Line 02∼04와 07에 각각 부여된 번호 순서에 따라 [그림 5- 21]의 link 변경
마지막으로 line 07에서 노드 x의 레퍼런스를 리턴 [주목해야 할 것] 서브트리들의 위치가 좌에서 우로 봤을 때, 항상 T1, T2, T3 순으로 유지

46 rotateLeft()는 오른쪽 방향의 서브트리가 높아서 불균형이 발생했을 때 왼쪽 방향으로 회전하기 위한 메소드
노드 n의 오른쪽 자식노드 x를 노드 n의 자리로 옮기고, 노드 n을 노드 x의 왼쪽 자식노드로 만들며, 이 과정에서 서브트리 T2가 노드 n의 오른쪽 서브트리로 이동 (a) 수행 전 (b) 회전 후 [그림 5-22] rotateLeft

47 Line 02∼04와 07에 각각 부여된 번호 순서에 따라 link 변경
마지막으로 line 07에서 노드 x의 레퍼런스를 리턴

48 LL-회전 (a) T1 또는T2에 새 노드 삽입 (b) LL-회전 후 h+2 30 h+1 20 h+1 h-1 20 h h 10
max(T1,T2) = h-1 (a) T1 또는T2에 새 노드 삽입 (b) LL-회전 후

49 LL-회전 (a) 노드 10의 왼쪽 서브트리(T1) 또는 오른쪽 서브트리(T2)에 새로운 노드 삽입
T1 또는T2의 높이 = h-1 노드 30의 왼쪽과 오른쪽 서브트리의 높이 차이 = 2 - 노드 30의 왼쪽(L) 서브트리의 왼쪽(L) 서브트리에 새로운 노드가 삽입되었기 때문 (b) 20이 30의 자리로 이동 30을 20의 오른쪽 자식으로 T3은 30의 왼쪽 자식으로 T3에 있는 키들은 20과 30 사이 값을 가지므로 T3의 이동 전후 모두 이진탐색트리 조건이 만족 LL-회전은 rotateRight() 메소드를 사용

50 [예제] LL-회전의 예

51 RR-회전 (a) T3 또는T4에 새 노드 삽입 (b) RR-회전 후

52 RR-회전 (a) 30의 왼쪽 서브트리(T3) 또는 오른쪽 서브트리(T4)에 새로운 노드 삽입 T3 또는T4의 높이 = h-1
노드 10의 왼쪽과 오른쪽 서브트리의 높이 차이 = 2 노드 10의 오른쪽(R) 서브트리의 오른쪽(R) 서브트리에 새로운 노드가 삽입되었기 때문 (b) 20이 10의 자리로 이동 10을 20의 왼쪽 자식으로 T2는 10의 오른쪽 자식으로 T2에 있는 키들은 10과 20 사이 값을 가지므로 T2의 이동 전후 모두 이진탐색트리 조건이 만족 RR-회전은 rotateLight() 메소드를 사용

53 [예제] RR-회전의 예

54 LR-회전 (a) T2 또는T3 에 새 노드 삽입 (b) LR-회전 후

55 LR-회전 (a) 20의 왼쪽 서브트리(T2) 또는 오른쪽 서브트리(T3)에 새로운 노드가 삽입 되어 T2 또는T3의 높이가 h-1이 됨에 따라 30의 왼쪽과 오른쪽 서브트리의 높이 차이가 2가 된 상태 30의 왼쪽(L) 서브트리의 오른쪽(R) 서브트리에서 새로운 노드가 삽입되었기 때문 LR-회전은 rotateLeft(10)을 먼저 수행한 후 rotateRight(30)을 수행

56 [예제] LR-회전의 예

57 RL-회전 (a) T2 또는T3 에 새 노드 삽입 (b) RL-회전 후

58 RL-회전 (a) 20의 왼쪽 서브트리(T2) 또는 오른쪽 서브트리(T3)에 새로운 노드가 삽입 되어 T2 또는T3의 높이가 h-1이 되고 10의 왼쪽과 오른쪽 서브트리의 높이 차이가 2가 된 상태 10의 오른쪽(R) 서브트리의 왼쪽(L) 서브트리에서 새로운 노드가 삽입되었기 때문 RL-회전은 rotateRight(30)을 먼저 수행한 후 rotateLeft(10)을 수행

59 [예제] RL-회전의 예

60 4종류의 회전의 공통점 회전 후의 트리들이 모두 동일 각 회전연산의 수행시간이 O(1)
각 그림(a)의 트리에서 10, 20, 30이 어디에 위치하든지, 3개의 노드들 중에서 중간값을 가진 노드, 즉, 20이 위로 이동하면서 10 과 30이 각각 20의 좌우 자식노드가 되기 때문 각 회전연산의 수행시간이 O(1) 각 그림(b)에서 변경된 노드 레퍼런스 수가 O(1) 개이기 때문

61 5.2.2 삽입 연산 AVL트리에서의 삽입은 2단계로 수행 1 단계: 이진탐색트리의 삽입과 동일하게 새로운 노드 삽입
2 단계: 새로 삽입한 노드로부터 루트로 거슬러 올라가며 각 노드의 서브트리 높이 차이를 갱신 이 때 가장 먼저 불균형이 발생한 노드를 발견하면, 이 노드를 기준으로 새 노드가 어디에 삽입되었는지에 따라 적절한 회전연산을 수행

62 AVL트리를 위한 Node 클래스

63 이진탐색트리의 put()과 거의 동일 Line 11: 노드의 높이 계산 Line 12: balance() 메소드를 호출하여 불균형이 발생하였을 경우 적절한 회전연산을 수행 추가 Line 11: tallerHeight(int a, int b): a와 b 중에서 큰 값을 리턴

64 balance() 메소드: 불균형 발생 시 회전연산으로 불균형 해소
현재 노드 n이 부모노드와 재 연결되기 바로 직전에 노드 n의 불균형 여부를 검사하고 적절한 회전연산으로 불균형을 해결

65 bf(n) > 1: 노드 n의 왼쪽 서브트리가 오른쪽 서브트리보다 높고, 그 차이가 1보다 크므로 (line 02) 불균형 발생
bf(n.left)가 음수: n.left의 오른쪽 서브트리가 왼쪽 서브트리보다 높아서 불균형 발생됨(line 03) Line 04: rotateLeft(n.left) 수행 Line 06에서 rotateRight(n) 수행 [LR-회전] bf(n.left)가 음수가 아닌 경우: line 06에서 [LL-회전] RR-회전과 RL-회전도 line 08∼13에 따라 각각 수행되어 트리의 균형을 유지 [참고] 현재 노드 n의 균형이 유지되어 있으면, if-와 else if- 문을 건너 뛰고 line 14에서 노드 n의 레퍼런스를 리턴

66 bf(n): (노드 n의 왼쪽 서브트리 높이) – (오른쪽 서브트리 높이) 리턴

67 [예제] 30, 40, 100, 20, 10, 60, 70, 120, 110을 순차적으로 삽입

68

69 5.2.3 삭제 연산 AVL트리에서의 삭제는 2단계로 진행 [1단계] 이진탐색트리에서와 동일한 삭제 연산 수행
[2단계] 삭제된 노드로부터 루트노드 방향으로 거슬러 올라가며 불균형이 발생한 경우 적절한 회전연산 수행 회전연산 수행 후에 부모노드에서 불균형이 발생할 수 있고, 이러한 일이 반복되어 루트노드에서 회전연산을 수행해야 하는 경우도 발생

70 (a) 삭제 전 (b) 삭제 후 노드 40에서 불균형 발생
30을 가진 노드의 삭제 (a) 삭제 전 (b) 삭제 후 노드 40에서 불균형 발생

71 삭제 후 불균형이 발생하면 반대쪽에 삽입이 이루어져 불균형이 발생한 것으로 취급하자.
[핵심 아이디어] 삭제 후 불균형이 발생하면 반대쪽에 삽입이 이루어져 불균형이 발생한 것으로 취급하자. 삭제된 노드의 부모노드 = p=, p의 부모노드 = gp, p의 형제노드= s라고 하면, s의 왼쪽과 오른쪽 서브트리 중에서 높은 서브트리에 마치 새 노드가 삽입된 것으로 간주 (a) LL-회전 (b) RR-회전 (c) LR-회전 (d) RL-회전

72 [예제] 40을 삭제

73 LR-회전 후 RL-회전 후

74 수행시간 AVL트리에서의 탐색, 삽입, 삭제 연산은 공통적으로 루트노드부터 탐색을 시작하여 최악의 경우에 이파리노드까지 내려가고, 삽입이나 삭제 연산은 다시 루트까지 거슬러 올라가야 트리를 1 층 내려갈 때는 재귀호출하며, 1 층을 올라갈 때 불균형이 발생하면 적절한 회전연산을 수행하는데, 이들 각각은 O(1) 시간 밖에 걸리지 않음 탐색, 삽입, 삭제 연산의 수행시간은 각각 AVL의 높이에 비례하므로 각 연산의 수행시간은 O(logN)

75 다양한 실험결과에 따르면, AVL트리는 거의 정렬된 데이터를 삽입한 후에 랜덤 순서로 데이터를 탐색하는 경우 가장 좋은 성능을 보임
이진탐색트리는 랜덤 순서의 데이터를 삽입한 후에 랜덤 순서로 데이터를 탐색하는 경우 가장 좋은 성능을 보임

76 5.3 2-3트리 2-3트리는 내부노드의 차수가 2 또는 3인 균형 탐색트리
차수가 2인 노드 = 2-노드, 차수가 3인 노드 = 3-노드 2-노드: 한 개의 키를 가지며, 3-노드는 두 개의 키를 가짐 2-3트리는 루트로부터 각 이파리노드까지 경로의 길이가 같고, 모든 이파리노드들이 동일한 층에 있는 완전한 균형트리 2-3트리가 2-노드들만으로 구성되면 포화이진트리와 동일한 형태를 가짐

77 [핵심 아이디어] 2-3트리는 이파리노드들이 동일한 층에 있어야 하므로 트리가 위로 자라나거나 낮아진다.
2-노드의 키가 k1이라면, 노드의 왼쪽 서브트리에는k1보다 작은 키들이 있고, 오른쪽 서브트리에는k1보다 큰 키들이 있다. k1과 k2를 가진 3-노드는 3개의 서브트리를 가지는데, 왼쪽 서브트리에는k1보다 작은, 중간 서브트리에는 k1보다 크고k2보다 작은, 오른쪽 서브트리에는k2보다 큰 키들이 있다.

78 2-3트리에서도 이진탐색트리에서의 중위순회와 유사한 방법으로 중위순회 수행
2-노드는 이진트리의 중위순회 방문과 동일 k1과 k2를 가진 3-노드에서는 먼저 노드의 왼쪽 서브트리에 있는 모든 노드들을 방문한 후에 k1을 방문하고, 이후에 중간 서브트리에 있는 모든 노드들을 방문 다음으로 k2를 방문하고 마지막으로 오른쪽 서브트리에 있는 모든 노드들을 방문한다. 따라서 2-3트리에서 중위순회를 수행하면 키들이 정렬된 결과를 얻음

79 5.3.1 탐색 연산 루트노드에서 시작하여 방문한 노드의 키들과 탐색하고자 하는 키를 비교하며 다음 레벨의 노드를 탐색
루트노드에서 시작하여 방문한 노드의 키들과 탐색하고자 하는 키를 비교하며 다음 레벨의 노드를 탐색 [예제] 80 탐색

80 5.3.2 삽입 연산 2-3트리에서의의 삽입을 수행하려면 먼저 탐색과 동일한 과정을 거쳐 새로운 키가 삽입되어야 할 이파리노드를 찾아야 이파리노드가 2-노드이면 그 노드에 새 키를 삽입 이파리노드가 3-노드이면 새로운 키를 저장할 수 없으므로(overflow), 이 노드에 있는 2 개의 키와 새로운 키를 비교하여 중간값이 되는 키를 부모노드로 올려 보내고, 남은 두 개의 키를 각각 별도의 노드에 저장 이 과정을 분리(Split) 연산이라고 한다.

81 분리 연산 (a) 삽입 전 (b) 분리 저장 후 중간값을 위로 (a) overflow가 발생된 노드에 3개의 키가 있을 때, k1 < k2 < k3이라면, (b) k1과 k3을 각각 2-노드에(하나는 기존 노드에 다른 하나는 생성하여) 저장하고, 중간값인 k2를 부모노드로 올려보내 k1과 k3의 분기점 역할을 하도록

82 부모노드로 올려 보내진 키는 이파리노드에서와 마찬가지로 자리가 있으면, 즉 부모노드가 2-노드이면, 부모노드에 저장하고 삽입 연산을 종료
부모노드가 3-노드이면 분리 연산을 다시 수행 위 과정은 루트까지 올라가면서 반복될 수 있다. 루트에서 노드 분리가 일어나면 2-3트리의 높이가 1 증가

83 [예제 1] 50의 삽입 (a) 삽입 전 (b) 삽입 후

84 [예제 2] 70의 삽입 (a) 삽입 전 (b) 분리 연산 수행 (c) 분리 연산 수행

85 5.3.3 삭제 연산 2-3트리에서의 삭제는 항상 이파리노드에서 이루어짐
만약 삭제할 키가 있는 노드가 이파리노드가 아닌 경우, 이진탐색트리의 삭제와 유사하게 중위 선행자 또는 중위 후속자와 교환한 후에 이파리노드에서 실질적인 삭제를 수행 2-3트리의 삭제: 이동(Transfer) 연산과 통합(Fusion) 연산 사용

86 이동 연산 이동 연산이란 키가 삭제되어 노드가 empty가 되었을 때, 이 노드의 형제노드와 부모노드의 도움을 받아 1 개의 키를 empty 노드로 이동시키는 연산 형제노드는 반드시 3-노드이어야 함 3-노드가 empty 노드의 왼쪽 형제노드라면, 2 개의 키 중에서 큰 키를 부모노드로 올려 보내고 부모노드의 키를 empty 노드로 내려 보냄 형제노드가 empty 노드의 오른쪽 형제노드인 경우, 2 개의 키 중에서 작은 키를 부모노드로 올려 보내고 부모노드의 키를 empty 노드로 내려 보냄

87 부모노드가 2-노드, 3-노드인 경우 이동 연산

88 통합 연산 노드가 empty일때 이동 연산이 불가능한 경우 empty 노드와 그의 형제노드를 1개의 노드로 통합하고, empty 노드와 그의 형제노드의 분기점 역할을 하던 부모노드의 키를 통합된 노드로 끌어내려 저장하는 연산 통합 연산과 분리 연산은 상호 역(Reverse) 연산 관계

89 부모노드가 2-노드, 3-노드인 경우 통합 연산

90 2-3트리의 삭제 연산 알고리즘 [1] 삭제할 키 k가 있는 노드x를 탐색
[2] if (x가 이파리노드이면), k를 노드 x에서 삭제한다. x를 삭제 후 empty가 아니면 알고리즘 종료. 만약 x가 empty인 경우, x의 형제노드들 중에 3-노드가 있으면 이동 연산을 수행하고, 그렇지 않으면 통합 연산 수행 [3] if (x 가 이파리노드가 아니면), k의 중위 선행자가 있는 노드 y와 중위 후속자가 있는 노드 z를 찾는다. [4] if (y 또는 z에서 이동 연산이 가능하면), 이동 연산 가능한 키를 k와 서로 교환하고 이동 연산을 수행하며, 동시에 k를 삭제한 후에 알고리즘을 종료 [5] if (y와 z 둘 다 이동 연산이 불가능하면), y나 z 중에서 임의로 하나를 선택한다. 그리고 선택한 노드의 키를 k와 서로 교환한 후 k를 삭제하고, 통합 연산 수행 통합 연산 수행 후 루트 방향으로 연속적인 통합 연산이 수행될 수도

91 [예제 1] 80을 삭제 (a) 80이 있는 노드 탐색 (b) 80을 삭제

92 [예제 2] 80을 삭제

93 [예제 3] 50을 삭제

94 수행시간 2-3트리의 탐색, 삽입, 삭제 연산은 각각 트리 높이에 비례하는 시간이 소요
2-3트리의 탐색, 삽입, 삭제 연산은 각각 트리 높이에 비례하는 시간이 소요 각 연산은 루트노드부터 이파리노드까지 탐색해야 하고, 삽입이나 삭제는 분리나 통합 연산을 수행하며 다시 루트노드까지 올라가는 경우도 있기 때문 단, 개별적인 분리 연산이나 통합 연산은 각각 트리의 지역적인 부분에서만 수행되므로 O(1) 시간만 소요 2-3 트리가 가장 높은 경우는 모든 노드가 2-노드인 경우이고, 이 때의 트리 높이 = log2(N+1)

95 트리의 모든 노드가 3-노드이면 트리의 높이가 최소이며, 높이는 log3N  0.63 log2N이다.
따라서 2-3트리의 탐색, 삽입, 삭제 연산의 수행시간은 각각 O(logN)

96 2-3트리는 이진탐색트리에 비해 매우 우수한 성능을 보이나, 2-3트리를 실제로 구현하기에 다소 어려움이 따름
구현이 어려운 이유는 노드를 2 개의 타입으로 정의해야 하고, 분리 및 통합 연산에서의 다양한 경우를 고려해야 하기 때문 3-노드에서는 키를 2회 비교하는 것도 고려해야 2-3 트리는 5.4절에서 설명할 좌편향(Left-Leaning) 레드블랙트리의 기본 형태를 제공

97 2-3-4 트리 2-3트리를 확장한 2-3-4트리는 노드가 자식노드를 4개까지 가질 수 있는 완전균형트리
2-3트리를 확장한 2-3-4트리는 노드가 자식노드를 4개까지 가질 수 있는 완전균형트리 2-3-4트리의 장점: 2-3트리보다 높이가 낮아 그 만큼 빠른 탐색, 삽입, 삭제 연산이 수행이 가능 2-3-4트리에서는 삽입 연산을 루트부터 이파리노드로 내려가며 4-노드를 만날 때마다 미리 분리 연산을 수행할 수 있기 때문에 다시 이파리노드부터 위로 올라가며 분리 연산을 수행할 필요가 없고, 따라서 보다 효율적인 삽입 연산이 가능

98 삭제 연산도 삽입 연산과 유사하게 루트로부터 이파리노드 방향으로 내려가며 2-노드를 만날 때마다 미리 통합 연산을 수행하므로 키를 삭제한 후 다시 루트 방향으로 올라가며 통합 연산을 수행할 필요 없음 그러나 이러한 삽입과 삭제 연산도 이론적으로는 2- 3트리의 수행시간과 동일한 O(log2N)

99 5.4 레드블랙트리 노드에 색을 부여하여 트리의 균형을 유지
탐색, 삽입, 삭제 연산의 수행시간이 각각 O(logN)을 넘지 않는 매우 효율적인 자료구조 일반적인 레드블랙트리(Intro. to Algorithms, CLRS): 삽입이나 삭제를 수행할 때 트리의 균형을 유지하기 위해 상당히 많은 경우를 고려해야 한다는 단점이 있으며, 이에 따라 프로그램이 복잡하고, 그 길이도 증가함 좌편향 레드블랙(Left-Leaning Red-Black, LLRB)트리: 삽입이나 삭제 시 고려해야 하는 경우의 수가 매우 적어 프로그램의 길이도 일반 레드블랙트리 프로그램의 1/5정도에 불과 일반적인 레드블랙트리는 부모 포인터(레퍼런스)를 사용하는 비재귀적인 알고리즘을 구현된다.

100 LLRB 트리는 AVL-트리, 2-3트리, 2-3-4트리, 일반 레드블랙트리보다 매우 우수한 성능을 가짐
Introduction to Algorithms (CLRS)에 소개된 레드블랙트리가 일반적으로 사용되며, 전문 프로그래머가 프로그램을 작성해도 적어도 400 line이나 든다.

101 [핵심 아이디어] LLRB트리는 2-3트리에서 3-노드의 두 개의 키를 두 노드로 분리 저장하고, 작은 키는 레드, 큰 키는 블랙으로 만든 형태와 같다. LLRB트리와 2-3트리의 관계

102 LLRB트리는 개념적으로 2-3트리와 같기 때문에 2- 3트리의 장점인 완전균형트리의 형태를 내포
LLRB 트리의 노드는 블랙 또는 레드의 두 가지 색 정보를 가지며, 노드와 부모노드를 연결하는 link의 색은 노드의 색과 동일 따라서 LLRB 트리에서는 link의 색을 별도로 저장 안함 노드 n의 왼쪽 자식노드는 레드이고 그 연결 link도 레드이며, n의 오른쪽 자식노드는 블랙이고 그 연결 link도 블랙

103 [정의] LLRB트리는 이진탐색트리로서 다음의 네 가지 조건을 만족한다.
루트노드와 null 은 블랙이다. 루트노드로부터 각 null까지 2개의 연속된 레드 link는 없다. (연속 레드 link 규칙) 루트노드로부터 각 null까지의 경로에 있는 블랙 link 수는 모두 같다. (동일 블랙 link 수 규칙) 레드 link는 왼쪽으로 기울어져 있다. (레드 link 좌편향 규칙)

104 RedBlack Tree Class

105 RedBlackTree 클래스는 Node 클래스를 내부(Inner) 클래스로 선언
Node 객체는 id(키), name(키에 관련된 정보), 왼쪽 자식과 오른쪽 자식을 각각 참조하기 위한 left와 right를 가지며, 노드의 색을 저장하기 위해 color를 가진다. 여기서 노드의 색은 노드의 부모와 연결된 link의 색과 동일하며, 색은 레드와 블랙 두 가지만을 사용하므로, boolean 타입을 사용 Line 01: Key와 Value는 generic 타입이고, Key는 비교 연산을 위해 자바의 Comparable 인터페이스를 상속 받으며, Comparable에 선언되어 있는 compareTo() 메소드를 통해 키를 비교 Line 02∼03: 구현 및 사용 편의를 위해 RED를 true로, BLACK을 false로 정의

106 Line 04: root는 트리의 루트노드를 참조
Line 05∼16: Node 클래스 Line 17: 트리가 empty일 때 true를 리턴하는 메소드 Line 18: isRed() 메소드는 노드 n이 레드이면 true를, 아니면 false를 리턴. 단, line 19에서 노드가 null인 경우에도 false를 리턴 Line 21이후: 탐색, 삽입, 최솟값 삭제를 위한 메소드 선언

107 탐색하고자 하는 Key가 k 일 때, 루트의 id와 k를 비교하는 것으로 탐색 시작
k가 id 보다 작은 경우에는 루트의 왼쪽 서브트리에서 k를 찾고, k가 id보다 큰 경우에는 루트의 오른쪽 서브트리에서 k를 찾으며, id가 k와 같으면 노드를 찾은 것이므로 찾아낸 노드의 Value, 즉, name을 리턴 왼쪽이나 오른쪽 서브트리에서 k를 탐색하는 것은 루트에서의 탐색과 동일 노드의 id를 k와 비교하는 line 04의 compareTo() 메소드는 id가 k 보다 작으면 음수, id가 k 보다 크면 양수, 같으면 0을 리턴

108 5.4.3 레드블랙트리의 기본 연산 LLRB 트리의 삽입, 삭제 연산을 위한 기본 연산
rotateLeft: 노드의 오른쪽 레드 link를 왼쪽으로 옮기는 연산 rotateRight: 노드의 왼쪽 레드 link를 오른쪽으로 옮기는 연산 flipColors: 노드의 두 link의 색이 같을 때, 둘 다 다른 색으로 바꾸는 연산 회전이나 색 변환 연산은 삽입과 삭제 연산을 수행하는 도중에 트리의 규칙에 어긋나는 부분을 수정하는데 이용

109 50을 n이라 할 때, 오른쪽 자식인 노드 x가 왼쪽으로 회전하여 n의 자리로 이동하고, 노드 색이 블랙으로 되며, n은 x의 왼쪽 자식으로서 레드 link로 연결

110 rotateRight는 노드 n의 왼쪽 레드 link를 오른쪽으로 옮기는 메소드이고, rotateRight()의 line 02∼06에 각각 붙여진 번호순으로link와 색이 변경

111 색 변환연산은 (a)에서 (b)로, 또는 (b)에서 (a)로 각각 수행될 수 있다.

112 삽입 연산

113 Line 01: put() 메소드는 line 05의 put() 메소드를 호출
Line 02: root가 line 05의 put() 메소드로 리턴되는 Node를 가리키도록 한다. Line 08과 09: n.left와n.right를put() 메소드가 리턴하는 Node와 각각 연결시키는데, 이는 새로 삽입된 노드로부터 루트노드까지 올라가기 위함  Line 12∼14: 새 노드를 삽입한 후에 발생할 수 있는 연속 레드 link문제를 해결하기 위해 rotateRight, rotateLeft, flipColors를 차례로 수행 마지막으로 호출이 리턴되는 line 02에서는 root가 루트노드를 가리키며, line 03에서 루트노드를 (레드인 경우도 있으므로) 블랙으로 만든 후 삽입 연산을 종료

114 [예제]

115 최솟값 삭제 연산 [핵심 아이디어] 루트노드로부터 삭제하는 노드 방향으로 레드 link를 옮기어 궁극적으로 삭제되는 노드를 레드로 만든 후에 삭제한다 루트로부터 삭제하는 노드 방향으로 레드 link를 옮기는 과정은 트리의 조건을 위반하지 않는 상태를 유지하며 진행 이를 위해 2 가지 방법으로 레드 link를 왼쪽 아래로 내려 보낸다. 다만 레드 link 좌편향 규칙에 위배되는 경우가 발생할 수 있으나 이는 삭제 후에 다시 루트 방향으로 올라가면서 수정

116 [case 1] n. left 와 n. left. left가 모두 블랙이고, 동시에 n. right
[case 1] n.left 와 n.left.left가 모두 블랙이고, 동시에 n.right.left도 블랙이면, flipColors(n)을 수행 [case 2] n.left 와 n.left.left가 모두 블랙이고, 동시에 n.right.left가 레드이면, n.right.left의 레드 link를 왼쪽 방향으로 보낸다.

117 Case 2는 다음과 같은 일련의 기본 연산을 통해 레드 link를 왼쪽 아래로 내려 보낸다.
flipColors(n) rotateRight(n.right) n n rotateLeft(n) flipColors(n)

118 다음은 두 가지 경우를 모두 고려한 moveRedLeft() 메소드이다.
Case 1과2의 공통된 첫 연산은 flipColors Case 2는 세 개의 연산(line 04∼06)이 추가로 필요

119 Line 06에서 (n. left == null)이면 노드 n이 최솟값을 가진 노드인 것으로, 이때 단순히 null을 리턴
Line 06에서 (n.left == null)이면 노드 n이 최솟값을 가진 노드인 것으로, 이때 단순히 null을 리턴. 그 이유는 노드 n이 레드 노드로 만들어졌기 때문에, 왼쪽자식이 null인 상태에서 오른쪽 자식노드가 존재할 수 없기 때문 만일 오른쪽 자식노드가 있다면, 이 노드는 블랙 또는 레드 오른쪽 자식노드가 블랙이면 동일 블랙 link 수 규칙에 위배되고, 레드이면 좌편향 레드 link 규칙에 위배되므로 어떤 경우에도 LLRB 규칙을 만족하지 못한다. 레드이면 좌편향 레드 link 규칙에 위배되므로 => 최솟값을 가진 노드의 오른쪽 자식노드는 moveRedLeft()가 젼혀 건드리지 않으므로, 처음부터 오른쪽 자식이 레드이었다는 모순

120 fixUp() 메소드는 레드블랙트리 규칙에 어긋난 부분을 수정

121 [예제] deleteMin() 의 수행 과정

122 수행시간 LLRB트리에서 삽입과 삭제 연산은 공통적으로 루트노드부터 탐색을 시작하여 이파리까지 내려가고, 다시 루트노드까지 거슬러 올라온다. 트리를 한 층 내려갈 때나 올라갈 때에 수행되는 연산은 각각 O(1) 시간 밖에 소요되지 않으므로 삽입과 삭제 연산의 수행시간은 각각 트리의 높이에 비례  N개의 노드를 갖는 레드블랙트리의 높이 h는 2log N 보다 크지 않다. 루트부터 이파리까지 블랙 link 수가 동일하므로 레드 노드가 없는 경우에는 h = log N이며, 레드 노드가 최대로 많이 트리에 있는 경우에도 레드 link가 연속해서 존재할 수 없으므로 h ≤ 2log N이다.

123 응용 레드블랙트리는 반드시 제한된 시간 내에 연산이 수행되어야 하는 경우에 매우 적합한 자료구조이다.
레드블랙트리는 반드시 제한된 시간 내에 연산이 수행되어야 하는 경우에 매우 적합한 자료구조이다. 실제 응용사례로는 logN 시간보다 조금이라도 지체될 경우 매우 치명적인 상황을 야기할 수 있는 항공 교통 관제(Air Traffic Control) 핵발전소의 원자로(Nuclear Reactor) 제어 심장박동 조정장치(Pacemakers) 등

124 레드블랙트리는 자바의 java.util.TreeMap과 java.util.TreeSet의 기본 자료구조로 사용되며,
C++ 표준 라이브러리인 map, multimap, set, multiset에도 사용되고, 리눅스(Linux) 운영체제의 스케줄러에서도 레드블랙트리가 활용

125 5.5 B-트리 다수의 키를 가진 노드로 구성되어 다방향 탐색(Multiway Search)이 가능한 균형 트리
[핵심아이디어] 노드에 수백에서 수천 개의 키를 저장하여 트리의 높이를 낮추자.

126 [정의] 차수가 M인 B-트리는 모든 이파리노드들은 동일한 깊이를 갖는다. 각 내부노드의 자식 수는 M/2 이상 M 이하이다. 루트노드의 자식 수는 2 이상이다.

127 5.5.1 탐색 연산 B-트리에서의 탐색은 루트로부터 시작된다.
방문한 각 노드에서는 탐색하고자 하는 키와 노드의 키들을 비교하여, 적절한 서브트리를 탐색 단, B-트리의 노드는 일반적으로 수백 개가 넘는 키를 가지므로 각 노드에서는 이진탐색을 수행 50 10 25 65 80 1 5 15 20 30 35 40 45 55 60 70 75 85 90 95

128 5.5.2 삽입 연산 B-트리에서의 삽입은 탐색과 동일한 과정을 거쳐 새로운 키가 저장되어야 할 이파리노드를 찾는다.
이파리노드에 새 키를 수용할 공간이 있다면, 노드의 키들이 정렬 상태를 유지하도록 새 키를 삽입 이파리노드가 이미 M-1개의 키를 가지고 있으면, 이 M-1개의 키들과 새로운 키 중에서 중간값이 되는 키(중간키)을 부모노드로 올려 보내고, 남은 M-1개의 키들을 1/2씩 나누어 각각 별도의 노드에 저장한다. [분리(Split) 연산]

129 삽입 45 5 10 20 50 1 2 6 7 12 14 16 25 30 35 40 55 60 65 70 45 중간키 5 10 20 35 50 1 2 6 7 12 14 16 25 30 40 45 55 60 65 70

130 20 1 2 12 25 10 6 14 45 7 50 16 5 30 40 35 55 70 60 65

131 5.5.3 삭제 연산 B-트리에서의 삭제는 항상 이파리노드에서 이루어진다.
만약 삭제할 키가 속한 노드가 이파리노드가 아니면, 이진탐색트리의 삭제와 유사하게 중위 선행자나 중위 후속자를 삭제할 키와 교환한 후에 이파리노드에서 삭제를 수행 삭제는 이동(Transfer) 연산과 통합(Fusion) 연산을 사용 이동 연산: 이파리노드에서 키가 삭제된 후에 키의 수가 M/2-1보다 작으면, 자식 수가 M/2보다 작게 되어 B- 트리 조건을 위반. 이 때 노드의 좌우의 형제노드들 중에서 도움을 줄 수 있는 노드로부터 1 개의 키를 부모노드를 통해 이동

132 5를 삭제하는 과정 20 1 2 12 25 10 6 14 45 7 50 16 5 30 40 35 55 70 60 65 20 6 10 35 50 1 2 5 7 12 14 16 25 30 40 45 55 60 65 70

133 20 6 10 35 50 1 2 5 7 12 14 16 25 30 40 45 55 60 65 70 20 6 12 35 50 1 2 7 10 14 16 25 30 40 45 55 60 65 70

134 통합 연산: 키가 삭제된 후 underflow가 발생한 노드 x에 대해 이동 연산이 불가능한 경우, 노드 x와 그의 형제노드를 1 개의 노드로 통합하고, 노드 x와 그의 형제노드의 분기점 역할을 하던 부모노드의 키를 통합된 노드로 끌어내리는 연산

135 7을 삭제하는 과정 20 5 12 35 50 1 2 7 10 14 16 25 30 40 45 55 60 65 70 20 5 12 35 50 1 2 7 10 14 16 25 30 40 45 55 60 65 70 언더플로우

136 20 35 50 언더플로우 12 1 2 5 10 14 16 25 30 40 45 55 60 65 70 12 20 35 50 1 2 5 10 14 16 25 30 40 45 55 60 65 70

137 12 20 35 50 1 2 5 10 14 16 25 30 40 45 55 60 65 70

138 5.5.4 B-트리의 확장 B*-트리는 B-트리로서 루트를 제외한 다른 노드의 자식 수가 2/3M∼M이어야 한다.
즉, 각 노드에 적어도 2/3 이상이 키들로 채워져 있어야 B-트리에 비해 B*-트리는 공간을 효율적으로 활용

139 B+-트리는 실세계에서 가장 널리 활용되는 B-트리

140 성능 분석 B-트리에서 삽입이나 삭제 연산의 수행시간은 각각 B- 트리의 높이에 비례. 차수가 M이고 키의 개수가 N인 B- 트리의 최대 높이는 O(log M/2 N)이다. B-트리는 키들의 비교 횟수보다 디스크와 메인 메모리 사이의 블록 이동(Transfer) 수를 최소화해야 B-트리의 최고 성능을 위해선 1 개의 노드가 1 개의 디스크 페이지에 맞도록 차수 M을 정함

141 실제로 B-트리들은 M의 크기를 수백에서 수천으로 사용
예를 들어, M = 200이고 N = 1억이라면 B-트리의 연산은4개의 디스크 블록만 메인 메모리로 읽어 들이면 처리 가능하다. 성능향상을 위해 루트는 메인 메모리에 상주시킨다.

142 응용 B-트리, B+-트리는 대용량의 데이터를 저장하고 유지하는 다양한 데이터베이스 시스템의 기본 자료구조로 활용
Windows 운영체제의 파일 시스템인 HPFS(High Performance File System) 매킨토시 운영체제의 파일 시스템인 HFS(Hierarchical File System)과 HFS+ 리눅스 운영체제의 파일 시스템인 ReiserFS, XFS, Ext3FS, JFS 상용 데이터베이스인 ORACLE, DB2, INGRES와 오픈소스 DBMS인 PostgreSQL에서 사용

143 요약 이진탐색트리는 이진탐색의 개념을 트리 형태의 구조에 접목시킨 자료구조
이진탐색트리는 이진탐색의 개념을 트리 형태의 구조에 접목시킨 자료구조 이진탐색트리의 각 노드 n의 키가 n의 왼쪽 서브트리의 키들보다 크고, n의 오른쪽 서브트리의 키들보다 작다. 이진탐색트리 탐색, 삽입, 삭제 연산의 수행시간은 각각 트리 높이에 비례 AVL트리는 임의의 노드 x에 대해 노드 x의 왼쪽 서브트리의 높이와 오른쪽 서브트리의 높이 차이가 1을 넘지 않는 이진탐색트리 AVL트리는 트리가 한쪽으로 치우쳐 자라나는 것을 LL, LR, RR, RL-회전 연산들을 통해 균형을 유지 AVL트리의 탐색, 삽입, 삭제 연산의 수행시간은 각각 O(logN)

144 2-3트리는 내부노드의 차수가 2∽ 3인 완전 균형탐색트리
2-3트리의 탐색, 삽입, 삭제 연산의 수행시간은 각각 트리의 높이에 비례하므로 O(logN) 2-3-4트리는 2-3트리를 확장한 트리로 4-노드까지 허용 2-3-4트리에서는 루트로부터 이파리노드로 한번만 내려가며 미리 분리 또는 통합 연산을 수행하는 효율적인 삽입 및 삭제가 가능 레드블랙트리는 노드의 색을 이용하여 트리의 균형을 유지하며, 탐색, 삽입, 삭제 연산의 수행시간이 각각 O(logN)을 넘지 않는 매우 효율적인 자료구조

145 N개의 노드를 가진 레드블랙트리의 높이 h는 2logN보다 크지 않다. 탐색, 삽입, 삭제의 수행시간은 O(logN)
B-트리는 다수의 키를 가진 노드로 구성되어 다방향 탐색이 가능한 완전 균형트리 B*-트리는 B-트리로서 루트를 제외한 다른 노드의 자식 수가 2/3M∼M이어야 한다. B*-트리는 노드의 공간을 B- 트리보다 효율적으로 활용하는 자료구조 B+-트리는 키들만을 가지고 B-트리를 만들고, 이파리노드에 키와 관련 정보를 저장 B-트리는 몇 개의 디스크 페이지(블록)를 메인 메모리로 읽어 들이는지가 더 중요하므로 한 개의 노드가 한 개의 디스크 페이지에 맞도록 차수 M을 정함