트리(Tree)

[kdomo]

이론 정리

• 트리의 개념, 트리의 종류, 시간복잡도 등 이론 공부를 comments로 정리
• ~10월 2일

숙제

• 백준 트리 6문제

[kdomo]

트리의 개념

• 계층적인 자료를 표현하는데 적합한 자료구조
• 노드(node)와 간선(edge)"브랜치(Branch)라고도 불린다" 로 구성되어 있다.
• 제일 최상위에 위치한 노드를 루트노드(Root Node)라 부르고 나머지 노드들을 서브트리(Sub Tree)라고 부른다.
• 노드와 노드는 간선으로 연결되어 있다.

노드와의 관계

• 노드들 간에는 부모,형제,조상,자손 관계가 존재하고 레벨이 존재한다.
• B의 입장에서 A는 부모노드(Parent Node)이며 {B,C,D}는 A의 자식노드이다.
• 같은 부모노드를 가진 자식노드들은 형제노드라고 부른다. {E,F,G}는 B의 자식노드이므로 이 3노드들은 형제 노드이다.
• H와 I는 같은 레벨에 속해 있지만 부모노드가 다르므로 형제노드가 아니다.
• 조상(ancestor) 은 노드의 부모 노드들의 총 집합이다.
• 자손(descendant) 은 노드의 서브트리에 있는 모든 노드를 지칭한다. 자식노드와 자손노드는 다른것이다.
• 레벨(level) 은 루트 노드들로부터의 깊이를 뜻한다. (루트 노드의 레벨 = 1)
• 트리의 깊이(depth of tree) 는 트리에 속한 노드의 최대 레벨을 뜻한다.
• 노드의 차수(degree) 는 어떤 노드가 가지고 있는 자식 노드의 개수이다.
  • A의 경우 차수는 3 , C의 경우 차수는 1이다.
  • 단말노드는 차수가 0, 즉 자식이 없는 노드이다.
• 트리의 차수 는 트리가 가지고 있는 노드의 차수 중에서 가장 큰 값이다.

이진트리

• 공집합 이거나
• 루트 와 왼쪽 서브트리, 오른쪽 서브트리 로 구성된 노드들의 유한 집합
• 공집합의 의미는 연결된 자식노드 또는 서브트리가 없다는 뜻 이다.

이진트리의 성질

• n개의 노드를 가진 이진트리는 n-1개의 간선을 가진다.
• 부모와 자신간에는 정확하게 하나의 간선만이 존재한다.

• 높이가 h인 이진트리의 경우, 최소 h개의 노드를 가지고 최대 2^h-1개의 노드를 가진다

• n개의 노드를 가지는 이진트리의 높이는 최대n이거나 최소 log(n+1)이 된다.

이진트리의 분류

• 포화 이진트리는 각 레벨에 노드가 꽉 차있는 노드를 의미한다.
• 완전 이진트리는 높이가 k일때 레벨1부터 레벨 k-1까지는 노드가 모두 채워져 있고 레벨K부터는 왼쪽부터 오른쪽으로 순서대로 노드가 채워져있다. 마지막 레벨에 노드가 꽉 차 있지 않아도 되지만 중간에 빈 곳이 있어서는 안된다.
• 포화 이진트리는 완전 이진트리에 속하지만 그 역은 성립되지 않는다.

출처

[jinjinhee]

트리(Tree)

• 트리(Tree)는 그래프의 일종으로 정점과 간선을 이용하여 데이터의 배치 형태를 추상화한 자료구조이다.
• 서로 다른 두 노드를 연결하는 길이 하나뿐인 그래프를 트리라고 부른다.
• 힙(Heap)을 구현하는 방법 중 하나가 트리이다.

트리(Tree) 순회(내용 추가 필요)

• 전위 순회
• 중위 순회
• 후위 순회

이진 탐색 트리

• 이진 탐색 트리(Binary Search Tree)는 탐색을 위한 이진 트리 기반의 자료구조이다. 아래와 같은 특징을 갖는다.
• left node에는 부모노드보다 작은 값이 저장된다.
• right node에는 부모노드와 값이 같거나 큰 값이 저장된다.
• 모든 노드는 중복된 값을 가지지 않는다.

이진 탐색 트리 구현(python)

class Node:
    def __init__(self, data):
        self.left = None
        self.right = None
        self.data = data

    # 이진 탐색 트리에 노드 삽입
    def insert(self, data):
        if self.data:
            if data < self.data:
                if self.left is None:
                    self.left = Node(data)
                else:
                    self.left.insert(data)
            elif data > self.data:
                if self.right is None:
                    self.right = Node(data)
                else:
                    self.right.insert(data)
        else:
            self.data = data

    # 이진 탐색 트리에서 찾고자하는 값 탐색
    def search(self, want_word):
        if want_word < self.data:
            if self.left is None:
                return str(want_word) + " Not Found"
            return self.left.search(want_word)
        elif want_word > self.data:
            if self.right is None:
                return str(want_word) + " Not Found"
            return self.right.search(want_word)
        else:
            print(str(self.data) + ' is Found')

    # 이진 탐색 트리 출력
    def print_Tree(self):
        if self.left:
            self.left.print_Tree()
        print(self.data)
        if self.right:
            self.right.print_Tree()

그래프와 트리의 차이

[josuehyeon]

트리(tree)는 조상과 자손, 전체와 부분, 컴퓨터의 디렉터리 구조 등의 계층적인 자료를 표현하는데 이용되는 자료구조

###트리와 관련된 용어

*노드(node): 트리의 구성 요
*루트(root) 노드: 계층 구조에서 가장 높은 곳에 있는 노드
*서브 트리(subtree): 트리에서 루트 노드를 제외한 노드들
*간선(edge): 루트와 서브 트리를 연결하는 선
*단말 노드(terminal node/leaf node): 자식 노드가 없는 노드
*비단말 노드(nonterminal node): 자식 노드가 있는 노드
*차수(degree): 어떤 노드가 가지고 있는 자식 노드의 개수
*트리의 차수: 트리가 가지고 있는 노드의 차수 중에서 가장 큰 차수
*레벨(level): 트리의 각 층에 번호를 매긴 것 ({A(루트)} 레벨 1, {B, C, D}의 레벨 2, ...)
*트리의 높이(height): 트리가 가지고 있는 최대 레벨

###이진 트리(Binary Tree)

모든 노드가 2개의 서브 트리를 가지고 있는 트리를 이진 트리(binary tree)라고 한다. 이때 서브 트리는 공집합일 수 있다. 

<이진 트리의 순환적 정의>

공집합이거나루트와 왼쪽 서브 트리, 오른쪽 서브 트리로 구성된 노드들의 유한 집합으로 정의된다. 이진 트리의 서버 트리들은 모두 이진 트리여야 한다. 

<이진 트리의 성질>

*n개의 노드를 가진 이진 트리는 (n - 1) 개의 간선을 가진다. 

• 이진 트리에서 루트를 제외한 노드는 하나의 부모 노드만을 가짐
  *높이가 h인 이진 트리의 노드 개수: 최소 h개 / 최대 2^h - 1개
• 한 레벨에 적어도 하나의 노드가 존재해야 함
• 하나의 노드는 최대 2개의 자식을 가질 수 있음
• 레벨 i에서 최대 노드 개수: 2^(i - 1)
  *n개의 노드를 가진 이진 트리의 높이: 최대 n / 최소 ⎡log(n + 1)⎤
• 한 레벨에 적어도 하나의 노드가 존재해야 함
• 높이 h의 이진 트리가 가질 수 있는 최댓값 n <= 2^h - 1에서 양변에 log를 취하면 ⎡log(n + 1)⎤ <= h

<이진 트리의 분류>

*포화 이진 트리(Full Binary Tree)

• 트리의 각 레벨에 노드가 꽉 차 있는 이진 트리
• 높이가 k인 포화 이진 트리의 노드 개수: 2^k - 1
  *완전 이진 트리(Complete Binary Tree)
• 높이가 k일 때, 레벨 1부터 k - 1까지는 노드가 모두 채워져 있고 레벨 k에서는 왼쪽부터 오른쪽으로 노드가 순서대로 채워진 이진 트리
• 포화 이진 트리는 항상 완전 이진 트리이지만 그 역은 항상 성립하지는 않음
   

###이진 트리의 순회(Traversal)

이진 트리의 순회란 이진 트리에 속하는 모든 노드들을 한 번씩 방문하여 노드가 가지고 있는 데이터를 목적에 맞게 처리하는 것을 말한다. 이진 트리의 순회 방법은 크게 3가지로 나눌 수 있다. 
*전위 순회(preorder traversal): VLR
*중위 순회(inorder traversal): LVR
*후위 순회(postorder traversal): LRV

[jiyun828]

1.트리의 개념

1.1트리의 정의

노드(Node)와 브랜치(Branch)를 활용하여 구성한 데이터 구조
스택과 큐와 다르게 비선형 구조이다.
계층적 관계를 표현한다.
그래프의 한 종류이며 사이클이 없다.

- Height and Depth of the node move inversely.

1.2트리 관련 용어

• 트리의 구성 요소
  • 노드(Node)
    • 데이터를 저장하는 기본 요소
      ▪ 다른 노드와 연결되는 브랜치에 대한 정보도 포함
  • 간선(Edge)
  • 루트 노드 (Root Node)
    • 트리 최상단에 위치한 최상위 노드
  • 단말 노드 (Leaf Node = Terminal Node)
    • 하위 노드(자식 노드)가 없는 노드
  • 내부 노드 (Internal Node)
    • 단말 노드를 제외한 모든 노드로 루트 노드를 포함.
• 용어
  • 브랜치(Branch)
    • 상위 노드와 하위 노드를 연결하는 가지
  • 레벨(Level)
    • 최상위 노드를 Level 0이라고 할 때, 특정 레벨에 위치한 노드의 집합
  • 부모 노드(Parent Node)
    • 상위 노드
  • 자식 노드(Child Node)
    • 하위 노드
  • 형제 노드(Sibling Node)
    • 동일한 부모 노드를 가진 노드
  • 깊이(Depth)
    • 루트에서 어떤 노드에 도달하기 위해 거쳐야 하는 간선의 수
  • 높이(Height)
    • 하위 트리 개수 / 간선 수 (degree) = 각 노드가 지닌 가지의 수
  • 크기(Size)
    • 자신을 포함한 모든 자식노드의 개수
  • 노드의 차수(Degree of Node)
    • 각 노드가 지닌 가지의 수
  • 트리의 차수(Degree of Tree)
    • 트리의 최대 차수

1.3트리의 종류

• 이진 트리 (Binary Tree) vs 이진 탐색 트리 (Binary Search Tree)
  • 이진 트리(Binary Tree)
    • 노드의 최대 브랜치가 2개인 트리. 루트 노드를 중심으로 2개의 서브 트리로 나누어짐. 나뉜 두 개의 서브트리 모두 이진트리어야 함.
  • 이진 탐색 트리(Binary Search Tree: BST)
    • 이진 트리의 일종으로 데이터의 효율적인 탐색을 위해 사용.
    • 규칙:
      1.이진 탐색 트리의 노드에 저장된 키는 유일하다.
      2.부모의 키가 왼쪽 자식 노드의 키보다 크다. (왼쪽 노드는 해당 노드보다 작은 값)
      3.부모의 키가 오른쪽 자식 노드의 키보다 작다.
      4.왼쪽과 오른쪽 서브트리도 이진 탐색 트리이다.

1.4 트리의 적용 예시

주요 용도: 데이터 검색 (탐색)

1.5 이진 탐색 트리의 시간복잡도

• 트리의 높이(Depth)를 h라고 표기한다면, 시간복잡도는 O(h)
• 노드의 개수가 n일 때,
  • 트리의 높이 h=log2 ​n  에 가까움. 시간 복잡도는 O(logn) -> 빅오 표기법에서 log의 밑은 2
  • 한 번 판단할 때마다, 50%의 탐색할 후보를 제외할 수 있음. 시간이 단축 됨.

1.6 이진 탐색 트리의 장단점

• 장점: 탐색 속도를 개선할 수 있다.
• 단점:
  • 평균 시간 복잡도는 O(logn)이지만, 이는 트리의 양쪽이 모두 균등할 때의 평균 시간복잡도라고 할 수 있음.
  • 따라서, 트리가 한 쪽으로만 치우쳐져 있는 최악의 경우에는 링크드 리스트와 동일한 O(n)의 성능을 보여준다.

1.7 트리 횡단

• 리스트 (List) 데이터 구조의 경우,

모든 요소를 보았는 지 확인하기 위해 List 를 하나씩 살펴보기만 하면 됬음 - 트리 (Tree) 데이터 구조의 경우,

선형 (linear)이 아니므로 모든 것을 순회할 명확한 방법이 없다. (왼쪽으로 먼저 갈까? 오른쪽으로 먼저 갈까? Level 1먼저? Level 3먼저?) 그래서, 순회를 처리하는 데에 2가지 광범위한 접근 방식이 있다 : DFS (Depth-first Search) & BFS (Breath-first Search) In DFS, the philosophy is if there are children nodes to explore, exploring them is definitely the priority. In BFS, the priority is visiting every node on the same level we're currently on before visiting child nodes.

- 위 아래로 왔다 갔다 많이 하지만, 좌우로만 보면 in order 순서대로 하나씩 방문하기 때문에 In-order DFS라고 부름

- Post (~후에) : child node를 본 후가 되기 전까지는 parent node를 확인하지 못함 - 그래서 post-order 라고 부름.

[jonggking]

스터디끝나고 마크다운 공부해서 수정해놓겠습니다ㅎㅎ

트리(tree)

부모, 자식 노드를 갖고 데이터를 표현하는 자료구조.
자식이 하나만 있거나 없는 경우를 연결리스트라고 부른다. 연결리스트는 트리의 특별한 유형이라고 할 수도 있다.

이진트리(Binary Tree)

각 노드의 자식이 0-2까지

배열과, 리스트를 이용한 표현법(대표적. heap ⇒ 메모리에 낭비가있음)
노드와 링크를 클래스로 직접 표현. Node 클래스와 BT class를 이용한 표현법
class Node: def __init__(self, key): self.key = key self.parent = self.left = self.right = None def __str__(self): return str(self.key)

이진트리 순회(traversal)

이진트리의 노드를 빠짐없이 출력하는 세가지 방법

preorder(MLR): F B A D C E G I H
inorder(LMR): A B C D E F G H I
postorder(LRM): A C E D B I H G

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

특정 키 값을 찾는 연산을 효율적으로 할 수 있도록 조직화한 트리

정의
각 노드의 왼쪽 서브트리의 key 값은 노드의 key 값보다 작거나 같아야 한다.
각 노드의 오른쪽 서브트리의 key 값은 노드의 key 값보다 커야 한다.
따라서 수행시간은 O(h)이고, 검색 효율을 위해 h를 작게 유지하도록 함.

수행 시간 다 O(h) => h를 작게 하기 위해 균형이진탐색트리 => O(logN)
insert
search(find_loc)
delete(deleteByMerging, deleteByCopying)

균형이진탐색트리(Balanced BST)

:항상 트리의 높이가 O(logN) 정도로 보장이 되는 트리
ex) AVL트리, 레드블랙(Red-black)트리, (2,3,4)-트리, 스프레이(splay)트리

회전

AVL트리: 모든 노드에 대해서, 노드의 왼쪽 서브트리와 오른쪽 서브트리의 높이차가 1 이하인 BST