이진 트리에 순서 규칙을 얹은 자료구조. 모든 노드에 대해 왼쪽 서브트리는 그 노드보다 작은 값만, 오른쪽 서브트리는 큰 값만 갖는다. 이 규칙 하나로 찾을 값이 지금 노드보다 작은지 큰지만 보고 남은 절반을 통째로 버릴 수 있게 된다. 이분 탐색을 배열이 아니라 링크로 구현한 셈이다.
순서 규칙이 정해주는 것
규칙에서 바로 따라나오는 것이 몇 가지 있다. 최솟값은 가장 왼쪽, 최댓값은 가장 오른쪽에 있어서 찾을 것도 없이 한 방향으로 끝까지 내려가면 된다. 중위 순회하면 정렬된 순서로 나온다. 그리고 자기보다 큰 값 중 가장 작은 노드를 후임자(successor), 자기보다 작은 값 중 가장 큰 노드를 선임자(predecessor)라고 부르는데 삭제할 때 쓴다.
삽입과 삭제
삽입은 간단하다. 크면 오른쪽, 작으면 왼쪽으로 내려가다가 갈 자리가 비면 거기에 매단다.
삭제는 검색이 먼저 따라온다. 지울 노드를 찾아야 지우니까. 찾고 나면 자녀 수에 따라 세 갈래다. 자녀가 없으면 그 노드를 가리키던 참조를 끊고, 하나면 그 참조가 자녀를 가리키게 바꾼다. 둘이면 오른쪽 서브트리의 최솟값, 곧 후임자가 그 자리를 대신한다.
root.data = findMin(root.right);
root.right = delete(root.right, root.data);후임자여야 하는 이유는 그 값이어야 왼쪽은 전부 작고 오른쪽은 전부 크다는 규칙이 그대로 유지되기 때문이다. 왼쪽 서브트리의 최댓값인 선임자를 써도 똑같이 성립한다.
삽입과 삭제가 유연한 것이 이 구조의 장점이다. 배열처럼 원소를 밀어낼 필요 없이 참조만 바꾸면 된다. 값의 순서대로 순회할 수 있다는 것도 해시 테이블에는 없는 성질이다.
정렬된 입력이 만드는 최악
삽입, 삭제, 검색 모두 최선이 Θ(1), 평균이 O(log N), 최악이 Θ(N)이다. 평균이 로그인 이유는 한 번 비교할 때마다 남은 크기가 절반으로 줄기 때문이다.
문제는 최악의 N이다. 이건 드문 사고가 아니라 정렬된 데이터를 순서대로 넣으면 반드시 일어난다. 1, 2, 3, 4, 5를 차례로 넣으면 모든 노드가 오른쪽 자식만 갖는 연결 리스트가 된다. 그러면 트리를 쓰는 의미가 사라진다.
그래서 실무에서 쓰이는 것은 삽입과 삭제 때 회전으로 높이를 로그로 유지하는 균형 트리다. AVL 트리와 레드-블랙 트리가 그것이고, 최악에도 O(log N)을 보장한다.