트리란?
바이너리 트리
각 노드가 하나 혹은 2개의 자식 노드만을 가지고 있는 상태의 트리구조이다
- perfect binary trees
모든 노드가 2개의 노드를 가지고 있으며, 값이 채워져있는 형태의 바이너리 트리이다!
아주 효율적이다!
왜why??? 한 레이어 아래로 내려가면 노드의 수는 2배가된다
마지막 레벨의 모든 노드 수의 총합은 그전까지의 모든 노드의 수 총합 + 1이다
즉, 전체 노드의 절반이 있다
O(log N)
퍼펙트 바이너리 트리경우 각 레벨의 노드의 수를 아는 방법은 2^(level-1)이다
즉, 노드 수에 로그를 씌우면 몇번째 레벨인지 알 수 있다
레벨0은 1개 log1 = 0
레벨1은 2개 log2 = 1
방식은 모든 노드를 iterating하는 것이아닌 특정 조건에 의해 왼쪽, 오른쪽을 선택해서 레벨을 내려가는 것을 반복한다
예) 노래방책으로 노래를 고를때 '하루하루' ㄱ부터 안찾고 ㅎ이라는 조건으로 가서 찾는다
즉, O(n)보다 빠르며 O(log N)의 예시가 바이너리 서치트리이다
바이너리 서치 트리
특정값을 찾을때 유용하다 특정값?????? 해쉬테이블이 떠오르는데??
하지만 더 낫다 왜??? 해쉬테이블은 데이터간의 관계가 존재하지않다(단지, 키와 밸류만있다)
노드들간의 관계에 의거하여 자료가 분류되어있다(마치 폴더와 파일구조처럼!!)
규칙에 의해 오른쪽 > 왼쪽 노드, 각노드는 2개만 가진다면??
장점은 특정값을 빠르게 찾을수있다, 배열은 모든요소를 반복하기때문에 최악의 경우 O(n)이 된다
하지만, 오른쪽으로 치우치게되고 불균형한상태가되어 결국 모든 요소를 반복할수밖에 없으므로
균형을 잘 맞추는게 중요하다!!
바이너리 힙
레벨이 내려갈수록 값이 작아진다는 특징이있다
위아래의 관계이기 때문에 나눠서 탐색이 불가능하다
즉, O(n)이다. 최대값이나 최솟값을 찾는 경우에 아주 좋겠지?? O(1)
레퍼런스
For Peace