🦁_21.12.16 TIL

21년 12월 16일

📝 자료구조 및 알고리즘

📎 트리(Tree) 구조

• 트리 구조는 그래프의 일종으로, 여러 노드가 한 노드를 가리킬 수 없는 구조
  => 회로가 없고, 서로 다른 두 노드를 잇는 길이 하나뿐인 그래프
• 주로 이진 트리(binary tree)형태 구조로 많이 사용되고, 탐색 알고리즘 구현에 만힝 사용
• 트리 구조 시각화 : https://blog.penjee.com/5-gifs-to-understand-binary-search-tree/#binary-search-tree-insertion-node
• 출저 : https://ko.wikipedia.org/wiki/%ED%8A%B8%EB%A6%AC_%EA%B5%AC%EC%A1%B0

트리 용어

• Node : 트리에서 데이터를 가지고 있는 기본 요소
• Root Node(뿌리 노드) : 트리에서 가장 위에 있는 요소
• Parent Node(부모 노드) : 한 노드에 연결된 이전 노드
• Child Node(자식 노드) : 한 노드에 연결된 상위 레벨의 노드
• Leaf Node(terminal Node) : chlid Node가 없는 노드
• Sibling(형제) : 같은 Parent Node를 가진 노드
• Level : 노드의 깊이를 나타냄
  => 가장 위에 위치한 노드 = evel 0
  => 하위 Branch로 내려갈수록 level이 올라간다.
• Depth(깊이) : 한 트리에서 가질 수 있는 level
  

트리와 그래프

• 그래프는 순환을 한다.
  

📎 이진 트리

• 이진트리란 자식 노드가 최대 두 개인 노드들로 구성된 트리
• 컴퓨터 과학에서 이진 탐색 트리(BST:binary search tree)는 이진 트리 자료 구조로 다음과 같은 속성이 있다.
  • 각 노드에 값이 있다.
  • 값들은 전순서가 있다.
  • 노드의 왼쪽 서브트리에는 그 노드의 값보다 작은 값들을 지닌 노드들로 이루어져 있다.
  • 노드의 오른쪽 서브트리에는 그 노드의 값과 같거나 큰 값들을 지닌 노드들로 이루어져 있다.
  • 좌우 하위 트리는 각각이 다시 이진 탐색 트리여야 한다.