공대생은 공돌공돌

이진탐색트리의 높이(깊이)

• 최악의 경우 높이 n
• 랜덤하게 만들면
• (균형 탐색 트리)-높이가 O(log2n)을 보장

경사이진트리 = 최악의 이진탐색트리

이진탐색트리의 중위순회

• 이진탐색트리를 중위순회하여 데이터를 출력하면 정렬된 데이터를 얻게 된다

• 이진트리 = 루트 + 왼쪽 서브트리 + 오른쪽 서브트리
• 어떤 일반트리도 이진트리로 변환 가능하다
• 왼쪽에서 오른쪽 순서로 이동

최소노드의 개수

• 레벨에 하나씩만 노드가 있다는 가정하에
  최소노드의 수는 h + 1

최대노드의 수

 

• 최대노드의 수는 (2 ^ h+1) - 1

Tree = root + subtrees

• 루트 노드(root node) : 부모 노드가 없는 중심이 되는 노르[트리에서 단 1개만 존재]
  - ex) 1

• 서브 트리(sub tree) : 루트 노드를 제외한 나머지 노드
  - ex ) 2, 3, ..., 9 , 10
• 리프 노드(leaf node) : 자식 노드를 가지고 있지 않은 트리의 말단에 있는 노드
  - ex) 7, 8, 9, 10
  
  
• 부모 노드(parent node) : 어떤 노드와 간선으로 연결되어 있고 위에 있는 노드
  - ex) 2번 노드는 4,5 번 노드의 부모 노드
  
  
• 자식 노드(children node) : 어떤 노드와 간선으로 연결되어 있고 그 아래에 있는 노드
  - ex) 4,5번 노드의 부모는 2번 노드
  
  
• 형제 노드(sibling) : 같은 부모 노드를 가지는 노드
  - ex) 8,9번 노드는 5번 노드를 부모로 하는 형제 노드
  
  
• 노드의 크기(size) : 자신을 포함한 모든 자식 노드들의 개수
  
  
• 노드의 차수(degree) : 어떤 노드가 가지고 있는 자식 노드의 개수
  - ex) 4번 노드의 차수는 1
  
  
• 노드의 깊이(depth) : 루트 노드에서 어떤 노드까지 도달하기 위해 거치는 정점의 개수
  ex) 6번 노드의 깊이는 2이다
  
• 트리의 레벨(level) : 트리의 각 층에 번호를 매긴 것이다. 루트의 레벨은 0이다.
  - ex) 6번 노드의 레벨은 2다
  
  
• 트리의 높이(height) : 가장 깊이가 깊은 노드의 깊이
  - ex) 트리의 높이는 3이다
  - 교재에 따라서 root node의 Level이 1부터 시작하는 경우도 있다