Tree

Tree의 정의 및 용어

정의 : Graph와 비슷하지만, 단방향이며 cyclic하지 않음

용어

• degree(자식 갯수)
• level(0부터 시작하는 깊이)
• root(최상단 노드)
• leaf(자식이 없는 노드)

Binary Tree 유형

Full Binary Tree : 모든 노드가 0개 또는 2개의 자식을 가짐

Complete Binary Tree : 마지막 레벨을 제외하고 전부 노드가 채워져있는 이진 트리

Perfect Binary Tree : 모든 노드가 채워져있는 이진 트리

Binary Tree 종류

BST(Binary Search Tree) 이진탐색 트리

부노 노드를 기준으로 우측 노드의 값은 부모보다 작고 좌측 노드는 부모보다 큰 구조

Balanced Tree

형제 노드끼리 서브트리의 높이가 1 이하로 차이나는 Tree

• Self Balancing binary search tree (삽입, 삭제 시 자동으로 정렬)
  • 레드블랙 트리
  • AVL
• B-Tree
• B+Tree (Binary는 아님)

Binary Heap

Binary Heap