Trees

binary search tree

트리(Tree)는 계층적인 구조를 나타내는 자료구조이다.
linked list 도 tree 의 일부분으로 볼수도 있다.
 
 
분기가 나눠지지 않은 트리는 링크드 리스트와 똑같이 생겼을 것이다.
 

---

 
tree 에는 2개의 포인터가 있다.
left and right
해당 노드의 값보다 작으면 left에 붙이고 크면 right에 붙인다.
결과적으로 부모노드의 오른쪽에 있는 노드들은 부모노드의 값보다 큰 값을 가지고 있는 노드들이 오게되고
왼쪽에는 부모노드보다 작은 노드들이 오게된다.

• 트리 자료구조의 구성요소
  • parent
  • child
  • leaf - 더이상 차일드가 없는 노드

 

---

 
tree에는 3가지 상태가 있는데,
full tree, perfect tree, complete tree 가 있다.
 

full tree
모든 노드들이 left, right이 있거나 아예 없는경우.
즉 left나 right 하나만 있어도 안됨.
 
 

perfect tree
대칭이 맞음
 
complete tree
왼쪽부터 채워지는 트리
 

---

 

Big O

O(log n), 최악의 경우 O(n)