해시트리, 이진트리 차이점을 알아보자

이진트리

자식 노드가 최대 2개인 트리

순회 방법

• preorder : 루트 - 왼쪽 - 오른쪽
• inorder : 왼쪽 - 루트 - 오른쪽
• postorder : 왼쪽 - 오른쪽 - 루트

배열로 구현 한다면 자식의 인덱스는 /2, 부모의 인덱스는 *2 이다.

어디에서 사용될까?
1. 효율적인 검색과 정렬을 위해 사용된다.
이진 탐색 트리와 이진 힙 구현에 사용한다.
이진 탐색 트리에서 탐색의 시간 복잡도는 logN이다.
2. 데이터를 분기 구조로 표현할 때 사용한다.

해시트리(머클트리)

데이터의 간편하고 확실한 인증을 위해 사용한다.

아래의 노드들을 해싱하면서 합쳐서 부모 노드를 만들어 가면서 루트 노드인 하나의 데이터로 만들어 주는 것이다.

루트 노드의 해시 값을 알면 데이터가 바꼈는지 검증할 수 있다.

여러 블록으로 나뉜 데이터를 전송할 때 데이터가 변조되지 않았음을 보장하는 용도로 사용된다.

블록체인에서 주로 사용