-
Data Structure - Tree / Binary Search TreeProgramming/Data Structure(자료 구조) 2019. 4. 7. 17:48
- Tree -
- Tree(트리)의 정의
- 트리는 노드로 이루어진 자료구조
- 최상위 노드는 루트(root) 노드라고 정의한다
- 노드와 노드를 연결하는 선을 edge(엣지 or 링크) 라고 정의한다
- 트리는 비선형 자료구조로 계층적인 관계를 가지고있다 (ex. Directory 구조)
- 트리는 그래프의 일종으로 사이클이 존재하지 않는 DAG(Directed Acyclic Graph), 즉 방향성이 있는 비순환 그래프의 일종이다
- Tree(트리)의 특징
- 루트 노드는 0개 이상의 자식 노드를 갖는다
- 자식 노드 또한 0개 이상의 자식 노드를 갖는다
- 부모 노드가 없는 노드는 최상위 노드(root)이다
- 최상위 노드에서 임의의 노드로 가는 경로는 유일하다 (다른 임의의 노드 간의 경로도 유일하다)
- 자식 노드는 한개의 부모 노드만 가질 수 있다
- 노드가 N개 이면 edge(엣지)의 개수는 N - 1개 이다.
- 트리의 순회 방법은 Pre-order, In-order, Post-order 3가지이다
- pre-order : 루트 노드에서 시작하여 노드 -> 왼쪽 서브 트리 -> 오른쪽 서브 트리 순으로 순환하는 방법
- In-order : 루트 노드에서 시작하여 왼쪽 서브 트리 -> 노드 -> 오른쪽 서브 트리 순으로 순환하는 방법
- Post-order : 루트 노드에서 시작하여 왼쪽 서브 트리 -> 오른쪽 서브 트리 -> 노드 순으로 순환하는 방법
- Tree(트리)의 이해를 위한 그림
-
그림에 대한 용어 설명
- Root : 최상위 노드
- Parent Node : 부모 노드
- Child Node : 자식 노드
- Sub-tree : tree구조 안에 있는 작은 tree구조
- Leaf Node : 자식이 없는 노드
- Siblings : 같은 부모를 갖는 노드 (형제 관계)
- Level : 트리의 특정 깊이를 가지는 노드의 집합
-
Binary tree(이진 트리)의 정의
- Binary tree는 tree의 일종이다
- 자식 노드의 개수가 최대 2개인 tree 구조를 Binary tree라고 한다
- 모든 트리가 Binary tree는 아니다
- Binary tree의 종류는 완전 이진 트리, 전 이진 트리, 포화 이진 트리 세가지이다.
-
Binary tree(이진 트리)의 종류의 특징
- 완전 이진 트리
- 마지막 레벨을 제외한 모든 노드가 꽉 차있는 이진 트리
- 마지막 레벨의 노드는 꽉 차지 않아도 되지만 노드가 왼쪽에서 오른쪽으로 채워져 있어야한다
- 마지막 레벨 h에서 가질 수 있는 노드의 개수는 (1 ~ 2h - 1)개 이다 - 전 이진 트리
- 모든 노드가 0개 or 2개의 자식 노드를 갖는 이진 트리 - 포화 이진 트리
- 모든 노드가 두개의 자식을 갖는 이진 트리
- 완전 이진 트리의 구조에서 마지막 레벨까지 모두 가득 차있는 형태
- 트리의 높이가 h라면 노드의 개수는 정확하게 2^(h - 1)개 이어야한다
- 완전 이진 트리
- Binary tree(이진 트리)의 이해를 위한 그림
- Binary Search Tree(이진 탐색 트리)의 정의
- 이진탐색트리란 이진탐색(binary search)과 연결리스트(linked list)를 결합한 자료구조의 일종
- 이진탐색의 효율적인 탐색 능력을 유지하면서도, 빈번한 자료 입력과 삭제를 가능하게끔 고안되었다
- 이진탐색의 경우 탐색에 소요되는 계산복잡성은 O(logn)O(logn)으로 빠르지만 자료 입력, 삭제가 불가능
- 연결리스트의 경우 자료 입력, 삭제에 필요한 계산복잡성은 O(1)O(1)로 효율적이지만 탐색하는 데에는 O(n)O(n)의 계산복잡성이 발생
- 두개의 장점만 합치려는 목적으로 만들어진 자료구조이다 - Binary Search Tree(이진 탐색 트리)의 이해를 위한 그림
- Pseudo - code(의사 코드)
//트리 구조를 이진 트리 형식으로 구현 //이차원 배열에 자식 노드를 저장하는 방식으로 구현 //이진 트리는 최대 두개의 자식을 갖기 때문에 //arr[i][0] = 왼쪽 자식 노드 , arr[i][1] = 오른쪽 자식 노드 <----------------------------------------------------> //pre-order, in-order, post-order 구현 //루트부터 순회 시작 //for문을 돌아 순회하도록 작성 //pre-order는 자신 -> 왼쪽 -> 오른쪽 순서 //이차원배열에 arr[i] -> arr[i][0] -> arr[i][1]순으로 값을 출력 //in-order는 왼쪽 -> 자신 -> 오른쪽 순서 //이차원배열에 arr[i][0] -> arr[i] -> arr[i][1]순으로 값을 출력 //post-order는 왼쪽 -> 오른쪽 -> 자신 순서 //이차원배열에 arr[i][0] -> arr[i][1] -> arr[i]순으로 값을 출력
'Programming > Data Structure(자료 구조)' 카테고리의 다른 글
Data Structure - Hash Table(해시 테이블) (0) 2019.04.07 Data Structure - Graph(그래프) (0) 2019.04.07 Data Structure - Stack / Queue / Linked List 정리 (0) 2019.04.04 - Tree(트리)의 정의