[패스트캠퍼스 수강 후기] {코딩테스트인강} 100% 환급 챌린지 11회차 미션

대표적인 데이터 구조7 : 트리

1. 트리 구조

   A. 트리: NODE와 BRANCH를 이용해 사이클을 이루지 않도록 구성한 데이터 구조

   B. 실제로 어디에 많이 사용되는가

      트리 중 이진 트리 형태 구조 & 탐색 알고리즘 구현을 위해 많이 사용됨

2. 알아야 하는 용어

    A. NODE: 트리에서 데이터를 저장하는 기본요소

    B. ROOT NODE: 트리 맨 위에 있는 노드

    C. LEVEL: 최상위 노드를 LEVEL 0으로 했을 때 하위 BRANCH로 연결된 노드의 깊이

    D. PARENT NODE: 어떤 노드의 다음 레벨에 연결된 노드

    E. CHILD NODE: 어떤 노드의 상위 레벨에 연결된 노드

    F. LEAF NODE ( TERMINAL NODE) : CHILD NODE가 하나도 없는 노드

   G. SILBLING ( BROTHER NODE): 동일한 PARENT NODE를 가진 노드

   H. DEPTH: 트리에서 NODE가 가질 수 있는 최대 LEVEL

 

 

3. 이진트리와 이진탐색 트리

     A. 이진트리: 노드의 최대 BRANCH가 2인 트리

     B. 이진 탐색 트리 ( BINARY SEARCH TREE) = 이진 트리에 다음과 같은 추가적인 조건이 있는 트리

          -왼쪽 노드는 해당 노드보다 작은 값, 오른쪽 노드는 해당 노드보다 큰 값을 갖고 있음

 

4. 자료 구조 이진 탐색 트리의 장점과 주요 용도

      A.주요 용도: 데이터 검색

      B. 장점: 탐색 속도를 개선할 수 있음

         단점: 이진 탐색 트리 알고리즘 이해 후 살펴보자

         이진 트리와 정렬된 배열간의 탐색 비교

(출처: https://www.mathwarehouse.com/programming/gifs/binary-search-tree.php#binary-search-tree-insertion-node)

5. 파이썬 객체지향 프로그래밍으로 링크드 리스트 구현

   5.1 노드 클래스 만들기

   class Node:

           def __init__(self, value):

                      self.value =value

                      self.left = None

                      self.right = None

   5.2  이진 탐색 트리에 데이터 넣기

        이진 탐색 트리 조건에 부합하게 데이터를 넣어야 함

      class NodeMgmt:

           def __init__(self , value):

                      self.current_node = self.head

                      while True:

                                 if value < self.current_node.value:

                                    if self.current_node.left !=None:

                                       self.current_node = self.current_node.left

                                    else:

                                            self.current_node.left = Node(value)

                                            break

                                 else:

                                     if self.current_node.right !=None:

                                            self.current_node = self.current_node.right

                                    else:

                                self.current_node.right = Node(value)

                                            break

 

head = Node(1)

BST = NodeMgmt(head)

BST.insert(2)

강의에 대해 정확하게 알고 싶다면 

https://bit.ly/2FgOONG