[자료구조] 트리(Tree) 구조
mag1c
[자료구조] 트리(Tree) 구조CS/자료구조2023. 1. 17. 19:32@mag1c
Table of Contents
728x90
728x90

트리구조란?

한 노드에서 시작해서 다른 정점들을 순회하여 자기 자신에게 돌아오는 순환이 없는 연결그래프이다.

  • 회사의 조직도
  • 내 컴퓨터\C:\Program Files\.....

출처 : https://hanamon.kr/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-tree-%ED%8A%B8%EB%A6%AC/

 

 

트리 용어

용어 설명
루트(root) 노드 맨 위에 위치한 노드이며, 부모노드 라고 함
리프(leaf) 노드 자식이 없는 최하단 노드, 단말(terminal) 노드 라고도 함
내부(internal) 노드 리프노드가 아닌 노드, 가지(branch) 노드 라고도 함
간선/엣지/링크/브랜치 노드들끼리의 연결선
노드의 차수 한 노드가 가진 서브트리의 차수
트리의 차수 트리노드들의 차수 중 최대차수
서브트리(sub-tree) 트리에서 어떤 한 노드와 그 노드의 자손들로 이루어진 트리
레벨(level) 0이나 1부터 시작하며 높이를 정의함
높이(height) 트리에 존재하는 서로 다른 레벨의 총 개수
깊이(depth) 루트노드부터 현재노드까지 오는데 거치는 간선의 개수
부모-자식(parent-child) 관계 루트노드를 제외한 모든노드는 하나의 부모를 갖는다.
형제(sibling) 관계 부모노드가 같은 노드들은 형제관계를 가진다

 

 

 

트리의 특징

  • 그래프의 한 종류이며, ‘최소 연결 트리’ 라고도 불린다.
  • 트리는 계층 모델 이다.
  • 트리는 DAG(Directed Acyclic Graphs, 방향성이 있는 비순환 그래프)의 한 종류이다.
  • loop나 circuit이 없다. 당연히 self-loop도 없다.(사이클이 없다)
  • 노드가 N개인 트리는 항상 N-1개의 간선(edge)을 가진다. (간선은 항상 (정점의 개수 - 1) 만큼을 가진다)
  • 루트에서 어떤 노드로 가는 경로는 유일하다.
  • 임의의 두 노드 간의 경로도 유일하다. (두 개의 정점 사이에 반드시 1개의 경로만을 가진다)
  • 한 개의 루트 노드만이 존재하며 모든 자식 노드는 한 개의 부모 노드만을 가진다.
  • 부모-자식 관계이므로 흐름은 top-bottom 아니면 bottom-top으로 이루어진다.
  • 순회는 Pre-order, In-order 아니면 Post-order로 이루어진다. 이 3가지 모두 DFS/BFS 안에 있다.
  • 트리는 이진 트리, 이진 탐색 트리, 균형 트리(AVL 트리, red-black 트리), 이진 힙(최대힙, 최소힙) 등이 있다.

 

 

 

트리의 순회

 

 

 

 

이진 트리(Binary Tree)

이진 트리는 2개 이하의 자식노드를 가진다. (자식노드가 없거나 1개의 자식노드만 가지는 것도 가능하다)

2개의 자식노드 중에서 왼쪽의 노드를 Left Node라고 하고, 오른쪽의 노드를 Right Node라고 한다.

 

편향 이진 트리 (Skewed Binary Tree)

편향 이진 트리는 하나의 차수로만 이루어져 있는 경우를 의미한다. 이러한 구조는 배열(리스트)와 같은 선형 구조이므로 'Leaf Node'(가장 아래쪽에 위치한 노드) 탐색 시 모두 데이터를 전부 탐색해야 한다는 단점이 있어 효율적이지 못하다. (이를 보완하기 위해 높이 균형 트리라는 것이 있다.)

 

 

포화 이진 트리 (Full Binary Tree)

포화 이진 트리는 'Leaf Node'를 제외한 모든 노드의 차수가 2개로 이루어져 있는 경우를 의미한다. 이 경우 해당 차수에 몇 개의 노드가 존재하는지 바로 알 수 있으므로 노드의 개수를 파악할 때 용이한 장점이 있다.

 

 

 

완전 이진 트리 (Complete Binary Tree)

포화 이진 트리와 같은 개념으로 트리를 생성하지만, 모든 노드가 왼쪽부터 차근차근 생성되는 이진 트리를 의미한다.

힙(Heap)은 완전 이진 트리의 일종이다

 

 

 

이진 탐색 트리 (Binary Search Tree)

이진 탐색 트리(Binary Search Tree)는 탐색을 위한 이진 트리 기반의 자료구조이다.

이진 탐색 트리는 데이터 탐색 시 노드를 이동하면서 탐색 가짓수를 절반으로 줄여나간다.

  • left node에는 부모노드보다 작은 값이 저장된다.
  • right node에는 부모노드와 값이 같거나 큰 값이 저장된다.
  • 모든 노드는 중복된 값을 가지지 않는다.

 

선언 방식

class BinarySearchTree {
    class Node {
        int data;	
        Node left, right;
 
        public Node(int item){
            data = item;
            left = right = null;
        }
    }
    
    Node root;
 
    BinarySearchTree() {
    	root = null;
    }
    BinarySearchTree(int value) {
    	root = new Node(value);
    }
 
    public static void main(String[] args){
        BinarySearchTree tree = new BinarySearchTree();
    }
}

 

1. 원소 탐색

아래의 그림은 원소 "10"을 찾는 과정이다

  • 탐색 수와 루트 노드의 데이터 비교
  • 탐색 수 > 루트 노드 : 오른쪽 트리 탐색
  • 탐색 수 < 루트 노드 : 왼쪽 트리 탐색
  • 계속해서 반복하며 리프노드까지 수를 찾는다. 

public Node search(Node root, int element){
    if (root==null || root.data==element)
        return root;
 
    if (root.data < element) 
       return search(root.right, element);
 
    return search(root.left, element);
}

 

2. 원소 삽입

  • 첫번째로 삽입하는 원소라면 root 노드로 지칭
  • 그 다음 원소를 삽입할 때, root 노드보다 작으면 왼쪽 트리, 크면 오른쪽 트리로 간선 연결해 추가
  • 기존 트리에 새로운 원소를 삽입한다면 search를 통해 자리를 찾아 추가

 

class BinarySearchTree {
    void insert(int element) { root = insertRec(root, element); } 
 
    Node insertRec(Node root, int element){
        if (root == null) {		
            root = new Node(element);
            return root;
        }
        else if (element < root.data)
            root.left = insertRec(root.left, element);
        else if (element > root.data)
            root.right = insertRec(root.right, element);
        return root;			
    }

	public static void main(String[] args){
        BinarySearchTree tree = new BinarySearchTree();
 
        /* 생성할 BST 트리 
              50
           /     \
          30      70
         /  \    /  \
       20   40  60   80 */
        tree.insert(50);
        tree.insert(30);
        tree.insert(20);
        tree.insert(40);
        tree.insert(70);
        tree.insert(60);
        tree.insert(80);
    }
}

 

 

 

3. 원소 삭제 

  • 자식이 없는 노드를 삭제할 경우(리프 노드)
  • 자식이 하나 있는 노드를 삭제할 경우
  • 자식이 두개 있는 노드를 삭제할 경우

 

a. 자식이 없는 노드를 삭제할 경우

 

 b. 자식이 하나 있는 노드를 삭제할 경우

 

c. 자식이 두개 있는 노드를 삭제할 경우

 

 

class BinarySearchTree {
    void deleteKey(int element) { root = deleteRec(root, key); } 
  
    Node deleteRec(Node root, int element)
    {
        if (root == null)
            return root;
  
        if (element < root.data)
            root.left = deleteRec(root.left, element);
        else if (element > root.data) 
            root.right = deleteRec(root.right, element);
        else {	
            if (root.left == null)
                return root.right;
            else if (root.right == null)
                return root.left;
  
            root.data = minValue(root.right);
  
            root.right = deleteRec(root.right, root.data);
        }
        return root;
    }
  
    int minValue(Node root) {
        int minv = root.data;
        while (root.left != null) { 
            minv = root.left.data;
            root = root.left;
        }
        return minv;
    }
}

 

 

 

 

 

728x90
300x250
저작자표시
mag1c
@mag1c :: 꾸준히 재밌게

2023.04 ~ 백엔드 개발자의 기록

포스팅이 좋았다면 "좋아요❤️" 또는 "구독👍🏻" 해주세요!

CS/자료구조 추천 글
more
image

티스토리툴바