헷갈리고 어려울땐 목차정리를 해보자! - 트리, B-Tree

1. 트리 구조의 정의

시험기간 공부 할 때, 아무런 계획도 없이 책을 처음부터 시험범위까지 본다면 과연 머리에 다 들어올까??

엄청 똑똑한 사람이 아니면 힘들지 않을까?

보통 책을 보면 목차가 나뉘어져있다. 

목차는 단원 - 주제 - 내용으로 나뉘어져 있고, 갯수만 보자면 1단원 안에 여러개의 주제들이 있고

그 주제들은 여러개의 내용들로 나뉘어져 있다.

이런 방식으로 공부하면, 마구잡이로 정리하는 것 보다는 머릿속에 정리되어서 남는다.

책 목차

 

이러한 데이터 정리방식이 컴퓨터의 자료구조에도 있다면 어떨까?

자료를 분류하고 다시 가져오는데 효율적이지 않을까?? 

이러한 데이터 정리 방식을 '트리구조'라고 칭한다.

그리고 상하관계가 있는 형태를 '계층'이 있는 자료구조 형태라고 한다.

 

2. 트리 구조를 왜 사용할까?

 - 위의 목차같이 계층을 형성하는 정보를 저장하기 위해 사용한다.

 -  배열처럼 모아진 정보이기 보다는  Linked List 와 비슷하게 주소값과 주소값이 연결된 '간선'으로 이어졌기 때문에 정보가 유기적 으로 이어져있다. 따라서 정보는 흩어져 있지만, 유기적으로 모아진 형태이므로 

 - 계층을 형성하는 정보는 정보의 검색이 쉬워지도록 한다.

    '낙타'를 검색한다고 했을때 여기저기 펼쳐져있는 정보의 바다에서 해당되는 키워드를 찾는것과

    '동물'이라는 키워드를 찾고 '포유류' 라는 키워드를 찾은 후 '4족 동물'의 키워드에서 '낙타'를 찾는 것 중 어느게 더 빠를까? 

Where is data what i want??

 

3. 트리구조의 특징

 - DAG(방향성이 있는 비순환 그래프)이다. 

   아래로 뻗어나가는 방향성이 있지만, 데이터가 순환하지 못하는 비순환 그래프의 한 종류이다.

  - 엣지의 수는 항상 노드의 갯수 -1 개 이다.

  - 부모-자식의 관계

    데이터를 찾을 때의 순회은 위>아래 혹은 아래>위로 이루어진다.

 

4. 트리 구조 용어

용어 정리

 - 루트 노드(root) : 부모가 없는 노드

 - 단말 노드(leaf) : 자식이 없는 노드

 - 내부 노드 : 자식이 있는 노드

 - 엣지 : 노드와 노드를 연결하는 선(서로의 주소값으로 연결)

 - 형제 : 같은 부모를 가지는 노드

 

5. 트리구조의 종류

자식의 최대수에 대한 비교

부모노드에서 갈라져 나오는 자식노드의 최대 갯수에 따라 종류를 구분한다.

그중에서도 데이터를 검색할 때 가장많이 사용하는 구조인 Binary Tree와 Binary Search Tree에 대해 알아보자

이진트리 와 이진검색트리

1)Binary Tree 

 - 자식노드의 최대 갯수가 2개인 Tree 

 

2) Binary Search Tree

  -  root노드의 데이터보다 큰 데이터들은 우측에 나열하고, 작은데이터들은 좌측에 나열하여, 데이터의 Search를 쉽게 한 Tree    

 

6. 의사코드를 이용해 이진트리구조 구현

 1) root

 // 데이터 + 다음데이터들의 위치값 (left , right)과 자신의 위치정보를(root or middle) 담아준다.

 

2) node 

 // 부모노드의 left 혹은 right 에 할당된다.

 // 데이터를 담아주고

 // 자식노드를 만들것이라면, 자신을 부모노드로 표시(middle)해주고 다음데이터의 위치값(left , right)을 담아준다.

 // 자식노드를 만들지 않는다면, 위치값 담아주지 않는다.

 

3) 데이터의 add 

 // 데이터의 추가는 leaf의 말단에만 가능하므로, 추가되길 원하는 부모노드 left 혹은 right 중 빈 곳에 데이터를 넣어준다.

 // Binary Search Tree 라면, 데이터값이 부모노드보다 크다면 right, 작다면 left에 할당해준다.

 

4)  데이터의 delete

// 부모노드의 left 정보나, right 정보를 삭제해준다

 

5) 데이터의 Output 

이진 트리 구조의 데이터 조회방법

 - InOrder (left , root(middle) , right)

  // 출력순서는 left > middle > right 순서로 이루어지도록 한다.

  // 단, 자식노드가 있다면  또 왼편 > 중간 > 오른편 의 순서로 데이터를 출력하고

  // 자식노드가 없으면 자기자신을 출력한다.

 

 - PreOrder(root(middle),left,right)

  //출력순서는 자식노드가 있다면, 자기자신 > 왼쪽 > 오른쪽순으로 이뤄지도록한다.

  // 자식노드가 없다면 자기자신을 출력하고, 부모노드로 이동하도록 한다.

 

 - PostOrder(left,right,root(middle))

  // 출력순서는 자식노드가 있다면 왼쪽 > 오른쪽 > 자기자신 순으로 이뤄지도록 한다.

  // 만약 자식노드가 없다면 자기자신을 출력하고, 부모노드로 이동하도록 한다.