개요
tree자료구조는 그 이름처럼 트리의 형태를 하는 자료구조이다.
구조
트리의 형태는 위 이미지와 같은데 각 동그라미 부분을 노드라고 하고 여기에 데이터가 저장된다.
이때 데이터 식별을 위해서 key와 데이터 저장소인 value를 설정할 수 있는데 이를 key-value구조라고 한다.
그리고 Tree를 탐색하는 과정을 순회한다. 라고 한다.
맨위 노드를 Root node, 맨아래에 있는 노드를 leaf node
하위 노드가 연결된 노드를 자식 node, 연결된 상위 node를 부모 node라고 한다.
여러가지 Tree
Binary Tree
한글로는 이진 트리라고 한다.
tree의 가장 기본적인 형태로 각 부모노드가 항상 2개 이하의 자식노드를 가져야 하는 트리형태이다.
Binary Search Tree
이진트리의 가장 일반적인 형태로 노드의 키를 기준으로 이미 정렬된 상태의 이진트리이다.
모든 노드의 키는 왼쪽 서브트리보다 크고 오른쪽 서브트리보다 작은 형태를 띈다.
가장 작은 키는 제일 왼쪽 부분 리프노드가 제일작고,
가장 큰 키는 제일 오른쪽 리프노드가 제일 큰 값을 갖는다.
AVL Tree
AVL트리는 위 이미지의 왼쪽트리처럼 불완전 트리 형태가 되면 균형조정을 통해 완전트리의 형태로 변환되고 정렬된다. 이를 트리회전이라고 한다.
시간 복잡도는 O(log n)이다.
DB데이터 검색에서 일부 사용되곤 하는 형태이다.
RB Tree
RB트리는 AVL트리와 동일하게 불균형을 감지하면 균형을 조정한다는 점에서 ㅂ슷하다.
하지만 RB트리가 트리 회전의 좀더 효율적이다.
RB트리는 노드마다 빨강또는 검정의 비트를 포함한다.
시간 복잡도는 AVL트리와 동일하게 O(log n)이다.
B Tree
B트리는 이진트리와는 다르게 자식노드를 3개 이상 가지는것이 가능한 트리이다.
B트리 또한 AVL, RB트리와 동일하게 자체적인 균형조정 기능을 갖춘 트리이다.
주로 파일 시스템에서 이러한 구조를 채택해서 사용한다.
Heap
이진트리의 한 종류이며 최대 값과 최소 값을 빠르게 접근해야 하는 경우 주로 사용된다.
힙에는 두가지 형태가 있다.
최대 힙: 루트 노드가 힙에서 제일 큰 값, 노드 각각의 값이 부모 노드보다 작거나 같도록 구성 됨
최소 힙: 루트 노드가 힙에서 제일 작은 값, 노드 각각의 값이 부모 노드보다 크거나 같도록 구성 됨
