JS TREE/Binary Search Tree

Tree

하나의 뿌리에서 뻗어나가는 형상.(조직도, 족보,Dom)

Node: 트리의 각 요소들

Root Node: 가장 상위의 노드

leaf Node,Terminal Node: 자식노드가 없는 최하위 노드

차수: 한 노드에 연결된 트리의 갯수. 차수가 2개면 이진트리

Prarent Node: 현재 노드에 연결되어있는 상위노드

Child Node: 하위의 자식노드.

Sibling Node(형제 노드): 같은 부모를 갖는 노드

Level: 루트 노드부터 해당 노드까지 경로를 찾는데 방문한 총 노드의 수 (아래 사진 트리구조는 레벨은 0부터3)

height(높이), depth(깊이): 트리의 최대 레벨수(아래 사진 높이 4)

 

 

 

이진 탐색 트리

-이진 트리이기때문에 모든 노드의 차수는 2개 이하여야한다.

왼쪽의 자식 노드는 부모 노드 보다 작아야하고

오른쪽 자식 노드는 부모보다 커야한다.

이진 탐색 트리는 평균적으로 이진 탐색과 똑같이 빠른 시간 복잡도를 가진다.

Big O

(평균)

삽입: O(log n)

삭제: O(log n)

검색: O(log n)

(최악의 경우)

삽입: O(n)

삭제: O(n)

검색: O(n)

단점: 데이터를 임의 접근 할 수 없다. (ex 트리의 6번째 원소를 찾을 수 없다.)

 ,트리가 균형이 맞지 않는 경우 데이터의 삽입과 삭제, 검색이 모두 O(n)만큼 소요된다. 한 쪽으로 치우쳐있으면 연결 리스트와 차이가 없어 장점이 없어진다. 

 

이러한 이진 트리의 단점을 해결하기 위해 :AVL트리, 레드-블랙 트리, 2-3 트리등이 있다.