[패스트캠퍼스 :: 코딩테스트 인강] 4주차 ① 트리 / 이진 트리

알고리즘/기술면접 완전 정복 올인원 패키지 Online

 

자료구조(트리) - 트리(Tree) - 1

자료구조(트리) - 트리(Tree) - 2

자료구조(트리) - 트리(Tree) - 3

자료구조(트리) - 트리(Tree) - 4

 

---

2021.03.13

정보처리기사 필기를 무사히 합격시켜놓고 일주일을 쉬다 보니

이번 주 자료구조 강의는 조금 늦었다. 

 

 

---

 

트리(Tree)

 

트리 (Tree) 구조

• 트리: Node와 Branch를 이용해서, 사이클을 이루지 않도록 구성한 데이터 구조

• 실제로 어디에 많이 사용되나?

  • 트리 중 이진트리 (Binary Tree) 형태의 구조로, 탐색(검색) 알고리즘 구현을 위해 많이 사용됨

 

• Node: 트리에서 데이터를 저장하는 기본 요소 (데이터와 다른 연결된 노드에 대한 Branch 정보 포함)

• Root Node: 트리 맨 위에 있는 노드

• Level: 최상위 노드를 Level 0으로 하였을 때, 하위 Branch로 연결된 노드의 깊이를 나타냄

• Parent Node: 어떤 노드의 다음 레벨에 연결된 노드

• Child Node: 어떤 노드의 상위 레벨에 연결된 노드

• Leaf Node (Terminal Node): Child Node가 하나도 없는 노드

• Sibling (Brother Node): 동일한 Parent Node를 가진 노드

• Depth: 트리에서 Node가 가질 수 있는 최대 Level

 

이진 트리 / 이진 탐색 트리 (Binary Search Tree)

• 이진트리: 노드의 최대 Branch가 2인 트리
• 이진 탐색 트리 (Binary Search Tree, BST): 이진 트리에 다음과 같은 추가적인 조건이 있는 트리
  • 왼쪽 노드는 해당 노드보다 작은 값, 오른쪽 노드는 해당 노드보다 큰 값을 가지고 있음!

 

 

<이진 탐색 트리에 데이터 넣기>

class NodeMgmt:
    def __init__(self, head):
        self.head = head
    
    def insert(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

 

<이진 탐색 트리 탐색>

class NodeMgmt:
    def __init__(self, head):
        self.head = head
    
    def insert(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
    
    def search(self, value):
        self.current_node = self.head
        while self.current_node:
            if self.current_node.value == value:
                return True
            elif value < self.current_node.value:
                self.current_node = self.current_node.left
            else:
                self.current_node = self.current_node.right
        return False        

 

---

다시 일상으로 돌아왔고, 

정보처리기사 실기 준비하면서 도움이 되기를 바라며

또 열심히 자료구조 알고리즘 강의를 수강해야겠다.

 

익숙한 듯 낯선 자료구조...

 

 

 

[패스트캠퍼스 100% 환급 챌린지 미션 중입니다.]

 

 

 

 

 

알고리즘 / 기술면접 완전 정복 올인원 패키지 Online. | 패스트캠퍼스