정렬 알고리즘은 아무리 빨라도 O(N logN)이다. 데이터를 자주 정렬해야 하면 데이터를 항상 정렬된 순서로 유지하는 편이 합리적이다.
정렬된 배열은 읽기에 O(1), (이진) 검색에 O(logN)이 걸린다. 하지만 삽입과 삭제가 상대적으로 느리다. 평균 시나리오에서 N/2 단계, 즉 O(N)이 걸린다.
해시 테이블은 연산이 빠르지만 순서를 유지하지 못하므로 알파벳순으로 목록을 정렬하는 애플리케이션에는 적절치 않다.
트리는 노드 기반 자료 구조이다. 하지만 연결 리스트와는 달리 트리의 각 노드는 여러 노드로의 링크를 포함할 수 있다.
이진 트리는 각 노드에 자식이 0개, 1개 혹은 2개 이다.
이진 탐색 트리는 다음의 규칙이 추가된 트리다.
class TreeNode {
constructor(value, left = null, right = null) {
this.value = value;
this.leftChild = left;
this.rightChild = right;
}
}
const node1 = new TreeNode(25);
const node2 = new TreeNode(75);
const root = new TreeNode(50, node1, node2);
이진 탐색 트리를 검색하는 알고리즘은 다음과 같다:
이진 탐색 트리 검색은 각 단계마다 검색할 대상이 남은 노드의 반으로 줄어든다. 처음 시작할 땐 루트의 자손 중 하나일 것이나, 오른쪽 자식을 선택하는 순간 왼쪽 자식과 왼쪽 자식의 자손은 모두 검색에서 제외된다. 따라서 O(logN)이다. 물론 최선의 시나리오인 포화 균형 이진 탐색 트리에서만 그렇다.
균형 이진 트리에 노드가 N개면 레벨(줄)이 약 logN개다. 노드가 N개인 트리에서 모든 자리마다 노드를 두려면 log(N) 레벨이 필요하다. 즉, 레벨을 새로 추가할 때마다 트리 크기가 두 배가 된다.
이진 탐색 트리 검색은 O(logN)인데 이는 정렬된 배열의 이진 검색과 효율성이 같다.
search(searchValue, node) {
// 기저 조건: 노드가 없거나, 찾고 있던 값이면
if (node === null || node.value === searchValue) return node;
if (searchValue < node.value) {
return this.search(searchValue,node.leftChild);
} else {
return this.search(searchValue, node.rightChild);
}
}
이진 탐색 트리 연산을 구현할 때 재귀를 많이 활용된다. 10장에서 배웠듯이, 재귀는 임의의 깊이만큼 들어가야 하는 자료 구조를 다룰 때 꼭 필요하다. 레벨이 무한한 트리가 그러하다.
search
함수는 찾는 값인 searchValue
와 검색 기반으로 사용할 node
를 입력으로 받는다. 처음 호출할 땐 node
가 루트 노드이다. 재귀 호출에선 node
가 트리 내 다른 노드일 수 있다.
함수에서 다루는 네 가지 조건 중 두 가지는 기저 조건이다. 노드에 찾고 있는 값이 들어있는 경우 해당 노드를 반환하고 더 이상 재귀를 호출하지 않는다.
자식 노드에 search
를 호출했는데 null
을 반환할 경우(실제로 기본값이 null
이기 때문에 null
을 반환한다.)는 searchValue
가 트리에 존재하지 않을 때 발생한다. 이때의 node
는 null
이므로, node
를 반환하는 것은 결국 null
을 반환하는 것인데, 이는 searchValue
가 트리 안에 없다는 뜻이므로 적절하다.
searchValue
가 현재 노드 값보다 작으면 searchValue
는 현재 노드보다 왼쪽에 있을 것이므로 왼쪽 자식에 대해 재귀적으로 호출하고, 크면 오른쪽에 있을 것이므로 오른쪽 자식에 대해 재귀적으로 호출한다.
이진 탐색 트리는 삽입에 가장 뛰어나다.
올바른 노드를 루트로부터 검색해 삽입한다.
삽입은 항상 검색에 한 단계 더 추가 된다. 즉, (logN) + 1단계가 걸리므로 O(logN)이다.
정렬된 배열은 검색에 O(logN), 삽입에 O(N)이다. 반면 이진 탐색 트리는 검색과 삽입 모두 O(logN)이 걸리므로 효율적이다. 데이터를 많이 변경할 애플리케이션이라면 특히 중요하다.
insert(value, node) {
if (value < node.value) {
if (node.leftChild === null) {
// 왼쪽 자식이 없으면 왼쪽 자식으로 값을 삽입한다.
node.leftChild = new TreeNode(value);
} else {
this.insert(value, node.leftChild);
}
} else if (value > node.value) {
if (node.rightChild === null) {
node.rightChild = new TreeNode(value);
} else {
this.insert(value, node.rightChild);
}
}
}
value
가 node
의 값보다 작은지 확인한다.
작다면 node
의 왼쪽 자손 어딘가에 삽입해야 한다는 뜻이다.
node
의 왼쪽 자식이 없다면 value
가 들어가야 할 자리가 그곳이므로 value
를 왼쪽 자식으로 삽입한다. 재귀 호출이 없으니 이 조건이 기저 조건이다.
자식이 있다면 그 자리에 값을 넣을 수 없으므로 왼쪽 자식에 대해 insert
를 재귀적으로 호출하면서 넣을 자리를 계속 검색한다. 언젠가는 자식이 없는 자손 노드에 도달하게 되고 그곳이 value
가 들어가야 할 자리다.
무작위로 정렬된 데이터로 트리를 생성해야 대개 균형 잡힌 트리가 생선된다. 완벽한 선형 트리는 최악의 경우 검색에 O(N)이 걸린다.
정렬된 데이터를 트리에 삽입하면 불균형이 심하고 덜 효율적일 수 있다. 오직 균형 트리일 때만 O(logN)이 걸린다.
따라서 정렬된 배열을 이진 탐색 트리로 변환하고 싶다면 먼저 데이터 순서를 무작위로 만드는 게 좋다.
삭제는 이진 탐색 트리에서 가장 어려운 연산이며 주의 깊게 실행해야 한다.
삭제된 노드와 그 노드의 모든 자손을 오름차순으로 정렬했을 때 삭제한 노드 다음으로 큰 수가 후속자 노드다.
후속자 노드에 왼쪽 자식은 없고 오른쪽 자식만 있을 수도 있다.
모든 단계를 종합하면 다음과 같다:
delete(valueToDelete, node) {
// 트리 바닥에 도달 해 부모 노드에 자식이 없으면 기저 조건
if (node === null) {
return null;
} else if (valueToDelete < node.value) {
// 삭제하려는 값이 현재 노드보다 작거나 크면
// 왼쪽 혹은 오른쪽 하위 트리에 대한 재귀 호출 반환값을
// 각각 왼쪽 혹은 오른쪽 자식에 할당
node.leftChild = this.delete(valueToDelete, node.leftChild);
return node;
} else if (valueToDelete > node.value) {
node.rightChild = this.delete(valueToDelete, node.rightChild);
return node;
} else if (valueToDelete === node.value) {
// 삭제하려는 값이 현재 노드인 경우
// 현재 노드에 왼쪽 자식이 없으면
// 오른쪽 자식(과 하위트리)을 부모의 새로운 하위트리로 반환
if (node.leftChild === null) {
return node.rightChild;
} else if (node.rightChild === null) {
return node.leftChild;
} else {
// 현재 노드에 자식이 둘이면
// 현재 노드의 값을 후속자 노드의 값으로 바꾸는 lift 함수를 호출
node.rightChild = this.lift(node.rightChild, node);
return node;
}
}
}
lift(node, nodeToDelete) {
// 이 함수의 현재 노드의 왼쪽 자식이 있으면 왼쪽 하위트리로 계속해서 내려가도록 재귀 호출
if (node.leftChild) {
node.leftChild = this.lift(node.leftChild, nodeToDelete);
return node;
} else {
// 왼쪽 자식이 없으면 현재 노드가 후속자 노드라는 뜻이다.
nodeToDelete.value = node.value;
return node.rightChild;
}
}
기저 조건은 노드가 실제로 존재하지 않을 때, 재귀 호출에서 존재하지 않는 자식 노드에 접근할 때이다.
valueToDelete
가 node
의 값보다 작다면 삭제할 값은 현재 노드의 왼쪽 하위 트리에 있는 것이다. delete
함수 자체는 결국 노드를 반환하므로, 왼쪽 하위 트리에 재귀적으로 호출하여 얻은 반환값을 왼쪽 하위 트리에 덮어 쓴다. 반대의 경우 역시 마찬가지다.
valueToDelete
가 node
의 값이라면, 즉 삭제할 값을 찾았다면 node
에 자식이 있는지 여부부터 판단한다.
node
에 왼쪽 자식이 없으면 node
의 오른쪽 자식을, node
에 오른쪽 자식이 없으면 node
의 왼쪽 자식을 함수의 결과로 반환한다.
그러면 반환한 트리는 이전 호출 스택의 왼쪽 혹은 오른쪽 자식 노드로 들어가게 되고, node
는 결국 삭제되는 셈이다.
삭제하려는 노드에 자식이 둘인 경우, lift
함수를 호출해 그 결과를 node
의 오른쪽 자식으로 넣는다.
lift
함수의 역할은 다음과 같다.
nodeToDelte
의 값을 후속자 노드의 값으로 덮어쓴다. 즉 후속자 노드를 올바른 위치에 넣는다. 후속자 노드 객체를 옮기는 게 아니라 삭제 중인 노드에 값을 복사할 뿐이다.rightChild
를 반환하거나, rightChild
에 왼쪽 자식이 없어 원래 rightChild
가 후속자 노드가 됐다면 null
을 반환한다.lift
의 반환값을 받아 node
의 오른쪽 자식으로 넣는다. 오른쪽 자식이 바뀌지 않거나, 오른쪽 자식이 후속자 노드라면 null
로 바뀐다.
트리 삭제도 일반적으로 O(logN)이다. 검색과 연결이 끊긴 자식을 처리하는 과정을 더해야 하기 때문이다.
이진 탐색 트리는 데이터 삽입과 삭제가 정렬된 배열보다 빠르므로 데이터를 수정할 경우 특히 효율 적이다.
책 제목 리스트를 관리하는 애플리케이션을 생성할 경우, 알파벳 순으로 출력할 수 있으면서 리스트를 계속 수정해야 한다면 이진 탐색 트리가 효율적이다.
이진 탐색 트리를 순서대로 출력하려면 어떻게 해야할까?
중위 순회를 하기 위해 traverse
이라는 재귀 함수를 생성한다. 함수는 다음과 같은 역할을 한다.
traverse
함수를 재귀적으로 호출한다.traverse
함수를 재귀적으로 호출한다.자식이 없는 노드에 traverse
를 호출하는 것이 기저 조건이며, 이때 함수는 return
만 실행한다.
traverseAndPrint(node) {
if (node === null) return;
this.traverseAndPrint(node.leftChild);
console.log(node.value);
this.traverseAndPrint(node.rightChild);
}
이렇게 되면 재귀 함수가 호출 스택에 쌓이며 순서대로 출력하게 된다.
트리 순회는 트리의 노드 N개를 모두 방문하므로 O(N)이다.
이진 탐색 트리는 정렬 순서를 유지하는 강력한 노드 기반 자료 구조이자 빠른 검색과 삽입, 삭제를 제공한다.