[CS] 자료구조 (2) : 이진탐색트리 (BST), B 트리, 힙 (Heap)

이진탐색트리 (BST)

노드의 왼쪽은 노드의 값보다 작은 값들, 오른쪽은 노드의 값보다 큰 값으로 구성한다.

목적 : 이진탐색 + 연결리스트 : 이 두가지를 합하여 장점을 모두 얻는 것이 이진탐색트리이다.

    - 이진탐색 : 탐색에 소요되는 시간복잡도는 O(logN), 삽입/삭제는 불가능

    - 연결리스트 : 삽입, 삭제의 시간복잡도는 O(1), 탐색하는 시간복잡도는 O(N)

시간 복잡도 : 삽입 및 삭제, 탐색까지 이상적일 때는 모두 O(logN) 가능하지만, 만약 편향된 트리면 O(N)으로 최악의 경우가 발생한다.

문제 : 편향된 트리 (정렬된 상태 값을 트리로 만들면 한쪽으로만 뻗음), 이를 바로 잡도록 도와주는 개선된 트리가 AVL, RedBlack 트리이다.

 

특징

 

1. 높이 : logN
2. 각 노드의 자식이 2개 이하이다.
3. 각 노드의 왼쪽 자식은 부모보다 작고, 오른쪽 자식은 부모보다 크다.
4. 중복된 노드가 없어야 한다. (검색 목적 자료구조이기 때문에 굳이 중복이 많은 경우에 트리를 사용하여 검색 속도를 느리게 할 필요가 없음, 트리에 삽입하는 것보다 노드에 count 값을 가지게 하여 처리하는 것이 훨씬 효율적)
5. 순회 방식 : 중위 순회로 정렬된 순서를 읽을 수 있다.

 

B Tree & B+ Tree

 

이진 트리는 하나의 부모가 두 개의 자식밖에 가지질 못하고, 균형이 맞지 않으면 검색 효율이 선형검색 급으로 떨어진다. 하지만 이진 트리 구조의 간결함과 균형만 맞다면 검색, 삽입, 삭제 모두 O(logN)의 성능을 보이는 장점이 있기 때문에 계속 개선시키기 위한 노력이 이루어지고 있다.

B Tree

데이터베이스, 파일 시스템에서 널리 사용되는 트리 자료구조의 일종으로, 이진 트리를 확장해서 더 많은 수의 자식을 가질 수 있게 일반화 시킨 것이다. 자식 수에 대한 일반화를 진행하면서, 하나의 레벨에 더 저장되는 것 뿐만 아니라 트리의 균형을 자동으로 맞춰주는 로직까지 갖추었다. (단순하고 효율적이며, 레벨로만 따지면 완전히 균형을 맞춘 트리)

 

장점

대량의 데이터를 처리해야 할 때, 검색 구조의 경우 하나의 노드에 많은 데이터를 가질 수 있다.

ex) 대량의 데이터는 메모리보다 블럭 단위로 입출력하는 하드디스크 or SSD에 저장해야하기 때문이다. 한 블럭이 1024 바이트면, 2바이트를 읽으나 1024바이트를 읽으나 똑같은 입출력 비용 발생. 따라서 하나의 노드를 모두 1024바이트로 꽉 채워서 조절할 수 있으면 입출력에 있어서 효율적인 구성을 갖출 수 있다. B Tree는 이러한 장점을 토대로 많은 데이터베이스 시스템의 인덱스 저장 방법으로 애용하고 있다.

 

특징

1. 노드의 자료수가 N이면, 자식 수는 N+1이어야 한다.
2. 각 노드의 자료는 정렬된 상태여야한다.
3. 루트 노드는 적어도 2개 이상의 자식을 가져야한다.
4. 루트 노드를 제외한 모든 노드는 적어도 M/2개의 자료를 가지고 있어야한다.
5. 외부 노드로 가는 경로의 길이는 모두 같다.
6. 입력 자료는 중복 될 수 없다.

B+ Tree

데이터의 빠른 접근을 위한 인덱스 역할만 하는 비단말 노드(not Leaf)가 추가로 있다. (기존의 B-Tree와 데이터의 연결리스트로 구현된 색인구조) B-Tree의 변형 구조로, index 부분과 leaf 노드로 구성된 순차 데이터 부분으로 이루어진다. 인덱스 부분의 key 값은 leaf에 있는 key 값을 직접 찾아가는데 사용한다.

 

장점

 

1. 블럭 사이즈를 더 많이 이용할 수 있다. (key 값에 대한 하드디스크 액세스 주소가 없기 때문)
2. leaf 노드끼리 연결 리스트로 연결되어 있어서 범위 탐색에 매우 유리하다.

 

단점

1. B-tree의 경우 최상 케이스에서는 루트에서 끝날 수 있지만, B+tree는 무조건 leaf 노드까지 내려가봐야 한다.

B Tree & B+ Tree 차이점

B Tree는 각 노드에 데이터가 저장된다.

B+ Tree는 index 노드와 leaf 노드로 분리되어 저장된다. (또한, leaf 노드는 서로 연결되어 있어서 임의접근이나 순차접근 모두 성능이 우수함)

 

B Tree는 각 노드에서 key와 data 모두 들어갈 수 있고, data는 disk block으로 포인터가 될 수 있다.

B+ Tree는 각 노드에서 key만 들어감. 따라서 data는 모두 leaf 노드에만 존재한다.

B+ Tree는 add와 delete가 모두 leaf 노드에서만 이루어진다.

 

힙 (Heap)

완전 이진 트리의 일종으로 여러 값 중, 최대값과 최소값을 빠르게 찾아내도록 만들어진 자료구조이다.

반정렬 상태이다.

힙 트리는 중복된 값 허용한다. (이진 탐색 트리는 중복값 허용X)

힙 종류

• 최대 힙(max heap) : 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진 트리
• 최소 힙(min heap) : 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진 트리

구현

힙을 저장하는 표준적인 자료구조는 배열로써, 구현을 쉽게 하기 위해 배열의 첫번째 인덱스인 0은 사용되지 않는다.

특정 위치의 노드 번호는 새로운 노드가 추가되어도 변하지 않는다.

(ex. 루트 노드(1)의 오른쪽 노드 번호는 항상 3)

 

부모 노드와 자식 노드 관계

왼쪽 자식 index = (부모 index) * 2
오른쪽 자식 index = (부모 index) * 2 + 1
부모 index = (자식 index) / 2

 

힙의 삽입

1. 힙에 새로운 요소가 들어오면, 일단 새로운 노드를 힙의 마지막 노드에 삽입한다.

2. 새로운 노드를 부모 노드들과 교환한다. 부모 노드는 자신의 인덱스의 /2 이므로, 비교하고 자신이 더 크면 swap하는 방식이다.

 

힙의 삭제

1. 최대 힙에서 최대값은 루트 노드이므로 루트 노드가 삭제된다. (최대 힙에서 삭제 연산은 최대값 요소를 삭제하는 것)

2. 삭제된 루트 노드에는 힙의 마지막 노드를 가져온다.

3. 힙을 재구성한다.