Tree, Binary Search Tree

# Tree

 - 그래프의 일종으로, 노드로 구성된 계층적 자료구조 

 - 최상위의 루트노드가 자식노드를 갖고, 그 자식노드가 또 자식노드를 갖는 형식

 - tree는 indegree가 무조건 1 :  1개의 부모노드만 가질 수 있음

 - 트리는 순환 구조를 가질 수 없음

 

 - node :  트리의 구성 요소 (ex. A, B, C...)

 - root node :  트리의 최상위 요소 (ex. A)

 - child node :  특정 요소의 바로 하위 요소 (ex. F, H, I에서 H, I는 F의 자식 노드)

 - parent :  특정 요소의 바로 상위 요소 (ex. F, H, I에서 F는 H, I의 부모 노드)

 - cibiling :  부모 노드가 같은 노드들 사이의 관계 (ex. D, E)

 - edge :  노드와 노드 사이를 연결하는 간선

 - leaf node :  자식 노드가 없는 노드, 트리의 맨 끝 말단 노드 (ex. G)

 - sub tree :  자신의 자식을 루트로 하는 트리 (ex. A의 서브트리는 B를 루트로 하는 왼쪽 서브트리, C를 루트로 하는 오른쪽 서브트리가 있음)

 

 

 ## depth & height

  - 트리의 높이(height) :  루트 노드부터의 높이이므로 루트 노드부터 시작해 계산, 1부터 시작

  - 트리의 깊이(depth) :  가장 깊이 존재하는 노드까지의 깊이이므로 루트 노드 ~ 리프 노드 사이의 깊이, 1부터 시작

  - 트리의 높이와 깊이는 루트 노드 ~ 리프 노드까지의 높이 / 깊이를 의미하므로 두 값은 같음 (ex. 위 그림의 트리 높이는 4)

  - 노드의 레벨 (level) :  트리의 특정 깊이를 가지는 노드들의 집합

  - 노드의 높이(height) : 리프 노드부터 가장 긴 경로에서의 간선의 수, 0부터 시작 (ex. B 노드의 높이는 2)

  - 노드의 깊이(depth) : 루트 노드부터 부터 가장 긴 경로에서의 간선의 수, 0부터 시작 (ex. B 노드의 깊이는 2)

 

 

 ## Tree & Graph의 차이

 

Tree	Graph
그래프의 일종으로, 방향성이 있는 계층적 자료구조	노드와 그 노드들을 연결하는 간선들로 구성된 자료구조
방향성을 가짐 (루트노드 -> 하위노드)	방향성이 있는 그래프도 존재하지만 무방향 그래프도 존재
부모노드 - 자식노드의 관계가 존재	부모노드 - 자식노드의 관계가 없음
순환 구조를 가질 수 없음	순환 구조를 가질 수 있음
루트 노드(최상위 노드)가 존재	루트 노드의 개념이 없음
노드가 N개인 트리는 항상 N-1개의 간선을 가짐	간선의 개수는 노드의 개수와 관계가 없음

 

 

 ## Tree의 Property

  - value :  해당 트리 노드가 갖는 고유한 값

  - children :  해당 트리 노드의 자식 노드의 모음

 

 

 ## Tree의 Method

 

  - insertNode :  특정 노드에 자식 노드를 추가

insertNode 연산
  1. 트리노드를 생성
  2. 부모 트리노드의 자식으로 생성한 노드를 추가
  

 

  - contains :  트리에 특정 값을 가지는 노드가 존재하는지 여부 반환

contains 연산 (value)
  1. 루트 노드부터 시작해 재귀를 돌며 value와 일치하는 값을 갖는 노드를 탐색
  2. 찾았다면 true / 찾지 못했다면 false 반환
  

 

 

 

 

# Binary Search Tree

 - 트리의 일종으로, 최대 2개의 자식 노드만 가질 수 있는 자료구조

 - 노드의 왼쪽 서브트리에는 노드보다 작은 값들이, 노드의 오른쪽 서브트리는 노드보다 큰 값들이 존재

 

 

 ## 이진 탐색 트리의 순회방식

 

   1. 깊이 우선 탐색 (DFS, Depth-First Search) :  한 노드를 방문하고 그 노드와 연결되어 있는 다른 노드들을 파고들어 탐색

      ˙  탐색시 모든 노드의 부모 노드들을 stack에 저장 (recursive)

 

     - 전위 순회 (Preorder Traversal) :  부모 → 좌 → 우

        ˙ 4 → 2 → 1 → 3 → 5 의 순서대로 위의 트리를 순회

        ˙ 전위 표기법 연산(연산자를 피연산자의 왼쪽에 두는 연산방법)에 효과적, 백트래킹

 

     - 중위 순회 (Inorder Traversal) :  좌 → 부모 → 우

        ˙ 1 → 2 → 3 → 4 → 5 의 순서대로 위의 트리를 순회

        ˙ 노드를 오름차순으로 방문

 

     - 후위 순회 (Postorder Traversal) :  좌 → 우 → 부모

         ˙ 1 → 3 → 2 → 5 → 4 의 순서대로 위의 트리를 순회

         ˙ 후위 표기법 연산(연산자를 피연산자의 오른쪽에 두는 연산방법)에 효과적

 

   2. 너비 우선 탐색 (BFS, Breadth-First Search) :  가까운 노드부터 순서대로 탐색

      ˙  4 → 2 → 5 → 1 → 3 의 순서대로 위의 트리를 순회

      ˙  탐색시 각 레벨의 노드들을 queue에 저장

 

 

 ## 이진 탐색 트리에서의 노드 삭제

 1. 삭제될 노드의 자식노드가 0개인 경우

    - 위 트리에서 11번 노드를 삭제

    - 11번 노드와 11번 노드의 부모인 12번 노드의 연결을 끊고, 11번 노드를 삭제

 

 2. 삭제될 노드의 자식노드가 1개인 경우

    - 위 트리에서 41번 노드를 삭제

    - 41번 노드를 삭제한 뒤, 41번 노드의 부모인 32번 노드와 41번 노드의 자식인 44번 노드를 이어 주었음

 

 3. 삭제될 노드의 자식노드가 2개인 경우

    - 위 트리에서 18번 노드 (루트 노드) 를 삭제

    - 왼쪽 서브트리에서 가장 큰 값 / 오른쪽 서브트리에서 가장 작은 값이 삭제된 값을 대신해 루트 노드가 됨

    - 왼쪽 서브트리에서 가장 큰 값 / 오른쪽 서브트리에서 가장 작은 값(루트 노드가 될 수 있는 값) 은 항상 0개 혹은 1개의 자식을 가짐

    - 그러므로 오른쪽 서브트리에서 가장 작은 값인 31번 노드가 제거된 18번 노드를 대신해서 루트 노드가 됨

 

 

 ## 이진 트리의 종류

 

  1. 정 이진트리 (Full Binary Tree)

    - 모든 노드가 0개 또는 2개의 자식 노드를 갖는 트리

 

  2. 완전 이진 트리 (Complete Binary Tree)

    - 마지막 레벨을 제외하고 모든 레벨이 완전히 채워져 있고, 마지막 레벨의 모든 노드들은 왼쪽에서 오른쪽으로 채워져 있음

 

  3. 포화 이진 트리 (Perfect Binary Tree)

    - 모든 레벨에 노드가 꽉 차서, 높이늘 늘이지 않는 이상은 노드를 추가할 수 없는 트리

    - 트리의 높이가 h일 때, 노드가  2^(h+1) -1  개로 최대 노드를 가짐

 

 

 ## Binary Search Tree의 Property

  - value :  해당 트리 노드가 갖는 고유한 값

  - left :  해당 트리 노드의 왼쪽에 위치한 자식 노드 (해당 노드보다 작은 값을 가짐)

  - right :  해당 트리 노드의 오른쪽에 위치한 자식 노드 (해당 노드보다 큰 값을 가짐)

 

 

 ## Binary Search Tree의 Method

 

  - insert

insert 연산 (value)
  1. 노드를 하나 생성
  2. 루트 노드부터 value 값을 비교하며 탐색 (recursive)
      탐색 중인 노드의 value > 생성된 노드의 value
        해당 노드의 오른쪽 서브트리로
      탐색 중인 노드의 value < 생성된 노드의 value
        해당 노드의 왼쪽 서브트리로
        

 

  - contains

contains 연산 (value)
  1. 루트 노드부터 value 값을 비교하며 탐색 (recursive)
      탐색 중인 노드의 value > value
        해당 노드의 오른쪽 서브트리로
      탐색 중인 노드의 value < value
        해당 노드의 왼쪽 서브트리로
        

 

  - inorder

inorder 연산 (callback)
  1. 탐색하는 위치에 노드가 없다면 리턴
  2. 노드의 왼쪽 서브트리로 들어가 inorder 반복 수행
  3. 탐색하는 위치에서 callback 함수 수행
  4. 노드의 오른쪽 서브트리로 들어가 inorder 반복 수행
  

 

  - preorder

preorder 연산 (callback)
  1. 탐색하는 위치에 노드가 없다면 리턴
  2. 탐색하는 위치에서 callback 함수 수행
  3. 노드의 왼쪽 서브트리로 들어가 preorder 반복 수행
  4. 노드의 오른쪽 서브트리로 들어가 preorder 반복 수행
  

 

  - postorder

postorder 연산 (callback)
  1. 탐색하는 위치에 노드가 없다면 리턴
  2. 노드의 왼쪽 서브트리로 들어가 postorder 반복 수행
  3. 노드의 오른쪽 서브트리로 들어가 postorder 반복 수행
  4. 탐색하는 위치에서 callback 함수 수행
  

 

 

 

 

 

참고 :

https://www.quora.com/What-is-the-difference-between-height-and-depth-of-a-tree

https://stackoverflow.com/questions/2603692/what-is-the-difference-between-tree-depth-and-height

https://gmlwjd9405.github.io/2018/08/12/data-structure-tree.html

https://www.geeksforgeeks.org/bfs-vs-dfs-binary-tree/

 

 

이진탐색트리를 애니메이션으로 볼 수 있는 웹사이트 :

http://btv.melezinek.cz/binary-search-tree.html