ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • Data Structure - Tree / Binary Search Tree
    Programming/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(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]순으로 값을 출력
    

     

    댓글 0

Designed by Tistory.