Part 1. 데이터 구조 - 3장 트리 데이터 구조

트리 데이터 구조 

뒤집혀 있는 나무 처럼 보인다. 

 

키-값 유형의 구조 

트리를 탐색하는 과정을 순회 (traversal) 라고 한다. 

<이진 트리> 

이진 트리 : 가장 많이 사용 되는 데이터 구조. 각 부모 노드가 항상 2개의 자식 노드와 연결 되어 있다. 

이진 트리의 가장 일반적인 유형은 이진탐색트리이다. 

이진 탐색 트리에서 모든 노드의 키는 왼쪽 서브 트리보다 크고 오른쪽 서브 트리보다 작다. 

트리에 노드 추가, 트리에서 노드 삭제, 노드를 선택해 탐색하고자 하는 키가 존재하는지 확인 가능 

 

<AVL 트리>  Adelson-Velsky and Landis 

불균형 이진트리, 단 하나의 자식 노드를 갖는 구조. 

트리의 균형을 조정하는 과정은 트리의 역할을 유지하되 가능한 한 최소 높이(자식 노드의 계층이 최소) 로 만드는 것이다. 

서브 트리 2개 사이에서 높이 차이를 감지하면 트리회전 이라는 균형 조정 과정을 수행 한다. 이러한 트리를 AVL 이진 트리 라고 한다. 

AVL 트리의 시간 복잡도는 O(logn) 이다. 

 

 

<RB 트리> red black 

RB 이진 탐색 트리는 자체적으로 균형을 조정 한다는 점에서 AVL 이진탐색 트리와 비슷 하지만, 트리의 구조 때문에 규형을 조정하는 과정에서 트리 회전수가 적어 AVL 트리보다 효율적이다. RB 트리의 시간 복잡도는 O(logn)이다. 

RB 트리는 노드마다 빨강 또는 검정으로 해석되는 비트를 포함 한다는 특징이 있다. 

 

<B 트리> 

컴퓨터 과학자들이 데이터베이스 시스템을 설계할때 사용하는 데이터 구조로, 자체적인 균형 조정 기능을 갖춘 트리유형. 

자식노드 3개 이상을 갖는 부모노드가 있다. 

 

 

<힙>

힙은 트리 기반 데이터 구조. 이진 트리데이터 구조의 한 종류, 값이 최대 혹은 최소인 노드에 빠르게 접근해야 하는 응용 프로그램에 적합. 2장의 우선순위 큐는 힙을 사용해서 규현할 수 있으며, 힙의 구조를 설계하는 방법에는 두가지가 있다. 

첫번째, 루트 노드가 힙에서 가장 큰 값이고, 노드 각각의 값이 부모노드의 값보다 작거나 같도록 구성된 힙을 최대힙 이라고 한다. 

두번째, 루트 노드가 힙에서 가장 적은 값이고, 노드 각각의 값이 부모 노드의 값보다 크거나 같도록 구성된 힙을 최소 힙 이라고 한다. 

 

* 힙 데이터 구조는 힙(heap memory)와 전혀 다른 개념이다. 힙 메모리는 프로그래머가 직접 관리해야 하는 메모리의 영역을 뜻한다. 

프로그래머가 작성한 코드에 따라 메모리 공간을 동적으로 할당하거나 해제하는 부분이기도 하다.