트리
- 나무를 닮은 자료구조ㅋㅋ
- 이용 현황
운영체제의 파일 시스템
XML을 다루는 DOM
검색 엔진, 데이터베이스 등등
* 트리의 구성 요소
뿌리(루트 노드) / 가지 / 잎(단말 노드)
자식 / 부모 관계
길이 / 깊이 / 레벨 / 높이 / 차수
* 트리 노드 표현
왼쪽 자식-오른쪽 형제 표현
typedef char ElementType;
typedef struct tagLCRSNode
{
struct tagLCRSNode* LeftChild;
struct tagLCRSNode* RightSibling;
ElementType Data;
} LCRSNode;
* 이진트리
- 모든 노드가 최대 2개의 자식을 가질 수 있는 트리
- 수식 이진 트리 / 이진 탐색 트리
종류
- 포화 이진 트리
- 완전 이진 트리
- 높이 균형 트리 : 왼쪽 하위 트리와 오른쪽 하위 트리의 높이가 1이상 차이나지 않는 이진 트리
- 완전 높이 균형 트리 : 왼쪽 하위 트리와 오른쪽 하위 트리의 높이가 같은 이진 트리
높은 성능을 위해 가능한 한 '완전한' 모습으로 배치
* 순회 종류
- 전위 순회
- 중위 순회
- 후위 순회
* 이진 트리 구현
typedef char ElementType;
typedef struct tagSBTNode
{
struct tagSBTNode* Left;
struct tagSBTNode* Right;
ElementType Data;
} SBTNode;
- 트리 소멸
반드시 잎 노드부터 자유 저장소에서 제거해야 함!!
* 수식 트리
수식을 표현하는 이진 트리
- 피연산자는 잎 노드
- 연산자는 루트 노드 or 가지 노드
- 후위 표기식을 이용해 트리 구축하는 것이 더 조음ㅋㅋ
사용하는 알고리즘
- 수식은 뒤에서 앞쪽으로 읽어나감
- 수식에서 제일 마지막에 있는 토큰은 루트 노드
* 분리 집합
: 서로 공통된 원소를 갖지 않는 집합들
교집합이 없기 때문에 서로 구분되어야만 하는 데이터 집합을 다룰 때 유용함
- 분리 집합은 자식이 부모를 가리킴
출처 : 뇌를 자극하는 알고리즘 (한빛미디어)
댓글