이진트리와 이진탐색트리

이진트리

이진트리는 각 노드가 최대 두 개의 자식 노드를 가지고 있는 트리 구조로서 부모 노드는 하나를 가지고 있으며 왼쪽 오른쪽 자식 노드를 가질 수 있다.

Root 노드는 맨 위의 부모 노드, Leaf 노드는 자식 노드가 없는 것을 말한다. 트리의 레벨은 맨 위 부모 노드가 레벨 0, 한 칸씩 내려갈수록 1씩 증가한다. 높이는 레벨+1을 생각하면 된다.

이진트리의 종류

정 이진 트리는 모든 노드가 0 또는 2개의 자식 노드를 갖고 있는 것
완전 이진트리는 마지막 레벨을 제외하고 모든 레벨이 채워져 있고 마지막 레벨은 최대한 왼쪽노드에 있는 트리
포화 이진 트리 모든 노드가 꽉 채워져 있는 트리

이진 탐색 트리

이진트리와 연결리스트를 결합한 구조.
이진트리와 차이는 탐색이 가능하다.

각 노드의 왼쪽 서브트리에는 부모 노드보다 작은 값으로 이루어진 노드로 구성되고, 오른쪽 서브트리에는 부모 노드보다 큰 값으로 이루어진다.
각 서브트리는 모두 이진탐색트리이다.

당신이 할수 있다고 믿든 할수 없다고 믿든 믿는 대로 될것이다. - 헨리 포드