정렬 알고리즘은 아무리 빨라도 O(NlogN)시간이 걸린다. 따라서 데이터를 자주 정렬해야 하면 다시 정렬하는 일이 없게 애초에 데이터를 항상 정렬된 순서로 유지하는 편이 합리적이다.

정렬된 배열은 순서대로 데이터를 유지하는 간단하면서도 효과적인 도구다. 또한 특정 연산에 매우 빨라서 읽기에는 O(1), 이진 검색을 사용할 때는 O(logN)이 걸린다. 하지만 삽입과 삭제가 상대적으로 느리다. 최악의 시나리오일 경우 N단계가 걸리고, 평균적으로 N / 2 단계가 걸린다. 즉 O(N)이므로 단순한 삽입이나 삭제치고는 느리다.

전반벅으로 빠른 속도를 내는 자료 구조를 원한다면 해시 테이블이 좋은 선택지다. 해시 테이블은 검색, 삽입, 삭제가 O(1)이다. 연산이 빠르지만 순서를 유지하지 못하므로 알파벳순으로 목록을 정렬하는 애플리케이션에는 적절치 않다.

15.1 트리

전형적인 연결 리스트는 각 노드마다 그 노드와 다른 한 노드를 연결하는 링크를 포함한다.

트리 역시 노드 기반 자료 구조이지만 트리의 각 노드는 여러 노드로의 링크를 포함할 수 있다.

• 가장 상위 노드를 루트라 부른다, 트리에 꼭대기에 해당한다.
• 트리에는 부모와 자식이 존재하며, 자손과 조상이 있을 수 있다.
  • 한 노드의 자손은 그 노드에서 생겨난 모든 노드이며, 한 노드의 조상은 그 노드를 생겨나게 한 모든 노드다.
• 트리에는 레벨이 있다. 각 레벨은 트리에서 같은 줄이다.
• 트리의 프로퍼티 property는 균형잡힌 정도를 말한다.
  • 모든 노드에서 하위 트리의 노드 개수가 같으면 그 트리는 균형트리다. 그렇지 않다면 분균형 트리라고 한다.

15.2 이진 탐색 트리

트리에 이진과 탐색이라는 수식어 두 개가 붙는다.

이진 트리는 각 노드에 자식이 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);

이진 탐색 트리로서 유효하려면 최대 왼쪽 자식 하나, 오른쪽 자식 하나만 있어야 한다.

15.3 검색

이진 탐색 트리를 검색하는 알고리즘은 다음과 같다.