[자료구조] 트리와 이진트리, 이진탐색트리(BST)

트리

그래프와 트리, 그리고 BST 87
균형잡힌 트리 : AVL 트리, 레드블랙트리 88

• 트리는 스택이나 큐, 어레이 같은 선형 자료구조가 아닌 비선형 자료구조.

• 계층적 관계(hierarchical RelationShip)을 표현하는 자료구조

  • 트리는 표현에 집중한다 무엇인가를 저장하고 꺼내야한다는 사고에서 벗어나 트리라는 자료구조를 보자

• 트리를 구성하고 있는 요소들

  • Node (노드) : 트리를 구성하는 각각의 요소
  • Edge (간선) : 트리를 구성하기 위해 노드와 노드를 연결하는 선
  • Root Node(루트 노드) : 최상위에 있는 노드
  • Leaf Node(Terminal Node, 단말 노드) : 하위에 자식 노드가 연결되어 있지 않은 노드
  • 내부 노드(Internal Node, 비단말 노드) : 단말 노드를 제외한 모드 노드, 루트 노드를 포함. 자식이 있는 노드

• 트리의 특징

  • 부모, 자식 계층 구조를 가짐
  • 트리에는 사이클이 존재할 수 없다 (사이클이 존재하면 트리가 아닌 그래프다 )
  • 노드의 개수가 N개면 간선은 N-1개. (V - 1 = E)
  • 임의의 두 노드 사이에 경로는 유일무이하게 존재하며, 경로는 유일한 한 경로 뿐이다.
• 

• 트리를 순회하는 방식 - 4가지
  1. 전위 순회 (pre-order)
     • 각 루트를 순차적으로 먼저 방문하는 방식
     • root -> 왼쪽자식 오른쪽자식
     • 1 -> 2 -> 4 -> 8 -> 9 -> 5 -> 10 -> 11 -> 3 -> 6 -> 13 -> 7 -> 14
  2. 중위 순회 (in-order)
     • 왼쪽 하위 트리를 방문한 후 루트를 방문하는 방식
     • 왼쪽자식 -> root -> 오른쪽 자식
     • 8 -> 4 -> 9 -> 2 -> 10 -> 5 -> 11 -> 1 -> 6 -> 13 -> 3 -> 14 -> 7
  3. 후위 순회 (post-order)
     • 왼쪽 하위 트리부터 하위를 모두 방문 후 루트를 방문하는 방식
     • 왼쪽자식 -> 오른쪽자식 -> 부모
     • 8 -> 9 -> 4 -> 2 -> 10 -> 11 -> 5 -> 13 -> 6 -> 14 -> 7 -> 3 -> 1
  4. 레벨 순회(level-order)
     • 루트(부모) 부터 계층 별로 방문하는 방식
     • 1 -> 2- > 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10 -> 11 -> 13 -> 14

트리 구현 자바 코드 - 접기/펼치기

public class Tree<T> {
    private Node<T> root;

    public Tree(T rootData) {
        root = new Node<T>();
        root.data = rootData;
        root.children = new ArrayList<Node<T>>();
    }

    public static class Node<T> {
        private T data;
        private Node<T> parent;
        private List<Node<T>> children;
    }
}

이진 트리(Binary Tree)

• * [이미지 출처](https://github.com/WooVictory/Ready-For-Tech-Interview/blob/master/Data%20Structure/%5BData%20Structure%5D%20Tree.md)

• 루트 노드를 중심으로 두 개의 서브 트리로 나누어짐 -> 자식이 두개여야만 함

  • 나누어진 서브 트리도 모두 이진 트리여야 한다.
  • 노드가 하나 뿐인 트리도 이진 트리의 정의에 만족한다

• 각 층별로 숫자를 매겨서 이를 트리의 레벨이라고 한다.

  • 레벨은 1부터 시작하고 루트 노드의 레벨은 1.
  • 트리의 최고 레벨을 가르켜 트리의 높이라고 한다.
    • 루트로부터 밑에 3개가 더있으면 1, 2, 3, 4 -> 4레벨

• 종류

  • 포화 이진 트리 (Full Binary Tree) : 모든 레벨이 꽉꽉 찬 이진 트리 -> 자식은 2개씩

    • 레벨별로 노드의 개수가 1, 2, 4, 8, 16 으로 늘어난다
    • 각 레벨별 최대 노드의 갯수는 2 ^ ( k - 1 )개 (k는 레벨)
    • 레벨 별 노드는 공비가 2인 등비 수열로 볼 수 있다,
    • 그러므로 높이가 h 인 이진트리가 가질 수 있는 최대 노드 수는 2 ^ h - 1 (h는 높이, 레벨)

• 완전 이진 트리 (Complete Binary tree) : 왼쪽에서 오른쪽으로 차곡차곡 채워진 이진 트리

  • 노드를 삽입할 때 왼쪽부터 차례대로 삽입하는 트리. 왼쪽이 비고 오른쪽이 들어가있는 트리는 완전 이진트리가 아님
  • 모든 노드가 0개 혹은 2개의 자식 노드만을 갖는 트리 = 정 이진 트리

• 편향 이진 트리(Skewed Binary Tree) : 모든 노드가 부모의 왼쪽으로 편향되어있거나 오른쪽으로 편향되어 있는 트리

• 규칙

  • 배열로 구성된 이진 트리는 노드의 개수가 n개이고 root가 0이 아닌 1 index에서 시작한다면
    • i 번째 노드에 대해서 parent(i) = i / 2
    • left child(i) = 2i
    • right child(i) = 2i + 1 의 index 값을 갖는다

이진 탐색 트리(BST, Binary Search Tree)

효율적인 탐색을 위해서는 어떻게 찾을까만 고민해서는 안된다.

효율적인 탐색을 위한 효율적인 저장방법이 무엇일까를 고민해야 한다.

이진 탐색 트리는 이진 트리의 일종이다.

이진 탐색 트리는 부모의 오른쪽 하위에는 부모 값보다 큰값인 노드만 저장되고, 왼쪽 하위에느 노드 값보다 작은 값만이 들어간다.

이진 탐색 트리의 목적은 이진 탐색의 장점과 연결리스트의 장점을 합친 것 -> 이진 탐색 + 연결 리스트

BST는 저장과 동시에 정렬을 하는 자료구조.

따라서 새로운 데이터를 저장할 때 일정한 규칙에 따라 저장을 하게 됩니다.

• 이진 탐색 - 탐색 소요 시간 O(log N)
  • 그러나 삽입 삭제가 불가능
• 연결리스트 -> 삽입, 삭제의 시간 복잡도는 O(1) 그러나 탐색 소요 시간이 O(n)
• 효율적인 탐색 소요시간 + 삽입 삭제도 빠르게 만들자는 목적

특징

• 각 노드의 자식이 2개 이하.

• 각 노드의 왼쪽 자식은 부모보다 작고, 오른쪽 자식은 부모보다 커야함

• 각 노드의 왼쪽과 오른쪽 서브 트리도 이진 탐색 트리이다.

• 데이터의 중복이 반드시 없어야 한다. - 노드에 저장된 키(데이터)값은 유일하다.

  • 검색 목적 자료구조인데, 중복이 많은 경우 트리를 사용하여 검색 속도를 느리게 할 필요가 없다.
    • 트리에 삽입하는 것보다 노드에 count를 가지게 하여 처리하는것이 효율적

• 이진 탐색 트리의 순회는 중위순회(in-order)방식 (왼쪽 - 루트 - 오른쪽)

  • 중위 순서로 정렬된 순서를 얻을 수 있다.

연산

• 검색(탐색) - O(log N) 제일 말단 노드에 원하는 값이 있을경우 높이(h)만큼의 노드를 탐색 -> O(n)
• 삽입
• 삭제
• 트리 생성
• 트리 삭제

시간 복잡도

• 균등 트리

• 삽입/삭제/찾기 연산 각각에 대해 모두 평균 시간복잡도는 O(logN), 최악의 시간복잡도는 O(N)

• 검색과 저장, 삭제의 시간복잡도는 모두 O(logn)이고, worst case는 한쪽으로 치우친 tree가 됐을 때 O(n)

  • 계속 작은 값만 들어오는 경우나, 계속 큰 값만 들어오는 경우

• 편향된 트리(정렬된 상태 값을 트리로 만들면 한쪽으로만 뻗음)는 시간복잡도가 O(N)이므로 트리를 사용할 이유가 사라짐

  • 배열보다 많은 메모리를 사용하며 데이터를 저장했지만 탐색에 필요한 시간 복잡도가 같게 되는 비효율적인 상황이 발생

• → 이를 바로 잡도록 도와주는 개선된 트리가 AVL Tree, RedBlack Tree

• 참고하면 좋다. 정리가 잘되어있다

• [트리(Tree)](https://github.com/gyoogle/tech-interview-for-developer/blob/master/Computer Science/Data Structure/Tree.md)

• 트리

• [Data Structure] Tree](https://github.com/WooVictory/Ready-For-Tech-Interview/blob/master/Data Structure/[Data Structure] Tree.md)

• [[Data Structure] B Tree & B+ Tree](https://github.com/WooVictory/Ready-For-Tech-Interview/blob/master/Data Structure/[Data Structure] B Tree %26 B%2B Tree.md)

• [B-Tree & B+Tree](https://github.com/gyoogle/tech-interview-for-developer/blob/master/Computer Science/Data Structure/B Tree %26 B%2B Tree.md)

• [이진탐색트리(Binary Search Tree)](https://github.com/gyoogle/tech-interview-for-developer/blob/master/Computer Science/Data Structure/Binary Search Tree.md)

• [[Data Structure] 이진 탐색 트리](https://github.com/WooVictory/Ready-For-Tech-Interview/blob/master/Data Structure/[Data Structure] 이진 탐색 트리.md)

• red-black-tree