트리(Tree): 방향성 있고 사이클이 없고 고립 영역이 없는 그래프
정점(Vertext or Node)과 간선(Edge or Branch)으로 표현할 수 있음
정점의 개수가 N이면 간선의 수는 N-1
트리의 용어
루트(Root): 트리 계층의 맨 위에 있는 노드, 부모가 없는 노드
레벨(Level): Root를 1로 출발해서 자신에 도달하는 데 걸리는 거리
높이(Height): 트리의 가장 높은 Level, 깊이(Depth)라고도 부름
가지(Branch): 부모와 자식간의 경로(간선)
조상(Ancestors): 자신에게 오기 위한 경로에 있는 모든 노드들
부모(Parent): Level N인 노드와 연결된 Level N-1인 노드
자식(Son): Level N인 노드와 연결된 Level N_+1인 노드
형제(Sibling): 같은 부모를 갖는 노드
차수(Degree)): 자식 수
트리의 차수: 트리의 모든 노드의 차수 중에 최대 값
단말(Terminal): 자식이 없는 노드, 차수가 0, Leaf라고도 부름
서브트리: 자식 노드를 Root로 하는 트리, 서브트리의 개수는 차수와 같다.
숲(Forest): 여러 개의 트리
이진 트리(Binary Tree): 트리의 차수가 2이하인 트리
Level N에 노드의 수는 최대 2의 (N-1)이다.
꽉 찬 이진 트리(Full Binary Tree): 높이가 H일 때 최대 개수로 구성한 이진 트리
높이 H일 때 노드의 개수는 2의 H승 – 1 개이다.
정이진 트리라고도 부름
완전 이진 트리(Complete Binary Tree): 노드를 삽입할 때 왼쪽 자식부터 추가하여 순서가 정해진 이진 트리
전 이진 트리라고도 부름
사향 트리(Skewed Binary Tree): 한쪽으로 기울어진 트리, 편향 트리라고도 부름
트리의 운행: 트리를 구성하는 모든 노드를 방문하는 방법
이진 트리의 운행은 루트를 방문하는 순서에 따라 전순위 운행, 중순위 운행, 후순위 운행으로 구분
전순위(Preorder) 운행: Root => Left 서브 트리 => Right 서브 트리
중순위(Inorder) 운행: Left 서브 트리 => Root => Right 서브 트리
후순위(Postorder) 운행: Left 서브 트리 => Right 서브 트리 => Root
스레드 이진 트리(Thread Binary Tree)
노드의 링크가 NULL인 부분을 트리 운행에 사용하는 이진 트리
왼쪽 링크가 NULL일 때 이전 노드의 위치를 기억
오른쪽 링크가 NULL일 때 이후 노드의 위치를 기억
인덱스를 이용한 트리
m-Way 검색 트리, B 트리, B+ 트리, B* 트리, 트라이(Trie)
인덱스 트리의 특징
인덱스를 통해 자료를 저장한 물리적 위치를 빠르게 탐색할 수 있다.
인덱스의 개수를 최소로 해야 효율이 높다.
m-Way 검색 트리
한 개의 노드에 m-1 개 Key와 m개의 서브 트리로 구성
검색 트리의 높이가 작아서 검색 시간을 줄일 수 있다.
균형을 유지하는 비용이 든다.
실제 자료까지의 탐색 길이가 같다.(색인부는 완전 균형 트리)
B 트리
루트(Root)와 단말(Termanal, Leaf) 노드를 제외한 모든 노드는 m/2~m 개의 서브 트리를 갖는 것을 보장
한 노드안에 키 값을 정렬 상태를 유지한다.
모든 단말 (Termanal, Leaf)노드는 같은 레벨이다.
루트(Root) 노드는 단말(Termainal, Leaf)가 아닐 때 두 개 이상의 서브 트리를 갖는다.
탐색, 추가, 삭제는 루트로부터 시작한다.
삽입, 삭제 요청에서 노드의 분열이나 합병이 이루어진다.
B+ 트리
단말 노드에는 리스트로 연결한 순차 집합
비단말 노드에는 인덱스 세트가 있고 인덱스 세트는 단말 노드에 있는 키 값을 찾는 경로만 제공
B트리보다 노드의 분열과 합병 연산을 줄일 수 있다.
B* 트리
트라이(Trie)
삽입, 삭제 요청에서 분열이나 합병이 발생하지 않는다.
탐색을 위해 키의 일부로 표현
트라이의 차수는 키 값을 표현하기 위해 사용하는 문자의 수(Radix)로 결정
키 값의 분포를 미리 예견할 수 있을 때 기억 장소를 절약
키 값들 사이에 별개의 전위(Prefix)수가 작을 때 적합
트리