2017/1/30

[S9S99]

진행 상황

• p.365 ~ p.378

  내용 정리

• Binary Trees
  • 트리 형태의 자료 구조
  • 정렬된 배열과 연결된 리스트의 장점을 가지고 있다.
  • 빠른 삽입, 삭제, 탐색
  • tree는 nodes가 edges로 연결된 형태를 말함.
  • 하나의 node에 여러개의 edge가 연결된 것을 multiway trees 라고 함
• Tree Terminology
  • Path : 노드의 결과 시퀀스
  • Root : 트리의 탑에 있는 node
  • Parent : 임의의 노드에 연결된 한단계 위 노드
  • Child : 임의의 노드에 연결된 한단계 아래 노드
  • Leaf : child가 없는 노드
  • Subtree : 하위트리
  • Visiting : 프로그램에서 제어를 위해 특정 노드에 도착
  • Traversing : 탐색을 위해 지정된 순서대로 노드를 방문하는 것
  • Levels : root는 0 자식으로 내려갈수록 1씩 증가
  • Key : key value
  • Binary Trees : 모든 노드가 최대 2개까지의 자식을 가진 트리
• Finding a Node
  • root에서 key 값을 비교해서 결과값에 도달할 때까지 자식노드를 타고 내려가는 형태
  • O(logN)