[CS] 자료구조 (2) : 이진탐색트리 (BST), B 트리, 힙 (Heap)
이진탐색트리 (BST) 노드의 왼쪽은 노드의 값보다 작은 값들, 오른쪽은 노드의 값보다 큰 값으로 구성한다. 목적 : 이진탐색 + 연결리스트 : 이 두가지를 합하여 장점을 모두 얻는 것이 이진탐색트리이다. - 이진탐색 : 탐색에 소요되는 시간복잡도는 O(logN), 삽입/삭제는 불가능 - 연결리스트 : 삽입, 삭제의 시간복잡도는 O(1), 탐색하는 시간복잡도는 O(N) 시간 복잡도 : 삽입 및 삭제, 탐색까지 이상적일 때는 모두 O(logN) 가능하지만, 만약 편향된 트리면 O(N)으로 최악의 경우가 발생한다. 문제 : 편향된 트리 (정렬된 상태 값을 트리로 만들면 한쪽으로만 뻗음), 이를 바로 잡도록 도와주는 개선된 트리가 AVL, RedBlack 트리이다. 특징 높이 : logN 각 노드의 자식이 2..
