: Node(값을 가진 노드)와 Edge(노드를 연결하는 간선)로 이루어진 자료구조
* 루트 노드 : 이미지 상에서 1을 가진 노드
* 모든 노드들은 0개 이상의 자식 노드를 가짐 (부모-자식 관계)
: 루트 -> 왼쪽 -> 오른쪽, 각 루트를 순차적으로 방문
1 - 2 - 4 - 8 - 9 - 5 - 10 - 11 - 3 - 6 - 13 - 7 - 14
: 왼쪽 -> 루트 -> 오른쪽, 왼쪽 하위 노드를 먼저 방문 후 루트를 방문
8 - 4 - 9 - 2 - 10 - 5 - 11 - 1 - 6 - 13 - 3 - 14 - 7
: 왼쪽 -> 오른쪽 -> 루트 , 왼쪽 하위 트리부터 오른쪽 하위 트리까지 방문 후 루트를 방문
8 - 9 - 4 - 10 - 11 - 5 - 2 - 13 - 6 - 14 - 7 - 3 - 1
: 루트부터 계층 별로 방문
1 - 2 - 3 - 4 - 5 - 6 - 7 - 8 - 9 - 10 - 11 - 12 - 13
: 기본적인 형태. 모든 노드의 차수가 2이하인 트리
: 모든 레벨이 꽉 찬 이진 트리
: 단말노드를 제외하고 모든 노드가 위에서 아래로, 왼쪽에서 오른쪽을 차곡차곡 채워진 트리
: 효율적으로 데이터를 탐색하도록 만든 자료구조, 이진 트리의 한 종류.
특징
1. 각 노드에 중복되는 키(데이터)가 없다
2. 루트 노드의 왼쪽 서브 트리는 루트노드보다 작은 데이터를 갖는 노드들로 이루어 진다.
3. 루트 노드의 오른쪽 서브 트리는 루트노드보다 큰 데이터를 갖는 노드들로 이루어 진다.
4. 좌우 서브 트리도 모두 이진 탐색 트리여야 한다.
: 트리의 높이가 h라면 O(h)의 시간 복잡도를 가진다. (중위순회 방식으로 데이터를 읽음)
: 이진탐색트리의 균형 문제를 해결하는 자료구조, 왼쪽 서브트리의 높이와 오른쪽 서브트리의 높이 차이가 1 이하가 되도록 함
: 이진탐색트리의 균형 문제를 해결하는 자료구조, 루트는 블랙으로 하며 노드가 레드이면 그 노드의 자식은 반드시 블랙이다.