🗒️ 책 & 강의 정리/🏗️ 누구나 자료구조와 알고리즘
15장 이진 탐색 트리로 속도 향상
데이터를 정렬하고 싶을 수 있다. 퀵 정렬 같은 정렬 알고리즘으로 데이터를 정리할 수 있지만 O(NlogN)이라는 시간이 필요하다. 따라서 데이터를 자주 정렬해야 한다면 애초에 데이터를 항상 정렬된 순서로 유지하는 편이 합리적이다. 정렬된 배열은 읽기 O(1), 검색 O(logN), 삽입 O(N), 삭제 O(N)이다. 순서를 유지하면서도 빠른 검색과 삽입, 삭제가 가능한 자료 구조가 필요하면 어떻게 해야 할까? 정렬된 배열도 해시 테이블도 완벽하지 않다. 이진 탐색 트리를 보자. 1. 트리 트리(tree)는 노드 기반 자료 구조이며, 트리의 각 노드는 여러 노드로의 링크를 포함할 수 있다. 가장 상위에 위치한 노드를 루트라고 부른다. 루트는 트리의 꼭대기다. 노드는 부모와 자식 노드가 있을 수 있다. 패..
