Data Structure - Tree / Binary Search Tree

- 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(log⁡n)으로 빠르지만 자료 입력, 삭제가 불가능
  - 연결리스트의 경우 자료 입력, 삭제에 필요한 계산복잡성은 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]순으로 값을 출력