[알고리즘] 이진트리, 이진탐색트리

이진트리 BT, binary tree

-각각의 노드의 자식 노드 수가 2개 이하로 구성되어 있는 트리

-정이진트리(full binary tree): 자식 노드가 0 또는 2개인 이진 트리를 의미한다.

완전이진트리(complete binary tree): 왼쪽에서부터 채워져 있는 이진 트리를 의미한다.

변질이진트리(degenerate binary tree): 자식 노드가 하나밖에 없는 이진 트리를 의미한다.

포화이진트리(perfect binary tree): 모든 노드가 꽉 차 있는 이진 트리를 의미한다.

균형이진트리(balanced binary tree): 모든 노드의 왼쪽 하위트리와 오른쪽 하위트리의 차이가 1이하인 트리이다. map, set을 구성하는 레드블랙트리는 균형이진트리 중 하나이다.

 

 

 

 

이진탐색트리 BST, binary search tree

-이진트리의 일종으로 노드의 왼쪽 하위트리에는 "노드의 값보다 작은값"이 있는 노드만 포함되고, 오른쪽 하위트리에는 "노드의 값보다 큰 값"이 들어있는 트리를 말한다. 이러한 특성 덕분에 데이터를 매우 효율적으로 검색할수있다.

-최악의 트리로 선형적인 트리(일렬로줄서는것)가 생길수도 있다.

그래서 삽입순서가 어떻건간에 균형잡힌 트리를 만드는, 트리의 노드들을 회전시키는 등의 방법을 통해서 이진탐색트리에서 발견된 트리로는 AVL트리, 레드블랙트리가 있다.