이진트리(Binary Tree)

이진 트리

각 노드가 최대 2개(0~2)의 자식 노드를 가지는 트리이지만 왼쪽 자식노드와 오른쪽 자신노드와 다릅니다.

*간단한 코드

class Node {
    int data;
    Node left;
    Node right;
}

정 이진 트리(full binary tree, strict tree)

모든 노드가 2개의 자식을 가지거나 자식이 없는 경우를 말합니다.

포화 이진 트리(Perfect Binary Tree)

모든 노드가 2개의 자식을 가지고 leaf노드가 같은 레벨

높이가 h인 포화 이진 트리에서 노드 갯수는 2^(k+1) -1

Leaf 노드의 갯수는 2^h

완전 이진 트리(Complete Binary Tree)

마지막 레벨을 제외하고 모든 노드가 채워져하고 이때 노드는 왼쪽에서 오른쪽으로 채워집니다.

이러한 특성으로 일차원 배열로 표현이 가능합니다.

이진 트리의 응용

힙

이진 탐색 트리(Binary Search Tree)

B-tree

AVL트리

이진 트리의 기본 연산

트리에 데이터 삽입, 삭제, 검색 그리고 탐색까지 합니다.