Merkle Tree 머클 트리(Merkle Tree)는 암호화된 해시 값을 기반으로 데이터 무결성을 효율적으로 검증하는 트리 구조이다. 블록체인, 분산 시스템, 파일 전송 프로토콜 등에서 널리 활용되며, 데이터 변조 탐지와 검증 효율성이 핵심 강점이다. 머클 트리는 분산 환경의 신뢰 문제를 해결하는 핵심 도구로, 블록체인의 성공을 가능케 한 기술이다. 데이터의 안전한 공유와 검증이 필요한 모든 시스템에서 그 가치를 발휘한다. 계층적 해시 구조 Leaf Node: 원본 데이터(트랜잭션, 파일 청크 등)의 해시 값으로 구성 (예: SHA-256). Non-Leaf Node: 자식 노드 두 개의 해시 값을 결합한 후 다시 해시화. Merkle Root: 최상위 노드의 해시 값으로 전체 데이터 집합을 대표. 예시: 4개 트랜잭션(A, B, C, D)의 머클 트리 구성 ...
Suffix Tree Suffix Tree는 주어진 문자열의 모든 접미사(suffix)를 압축된 트라이(trie) 형태로 표현한 트리 구조로, 각 간선은 문자열의 부분 문자열을 나타내며, 리프 노드는 접미사의 시작 위치를 나타낸다. https://www.geeksforgeeks.org/pattern-searching-using-suffix-tree/ 특징 모든 접미사를 트리 형태로 표현한다. 공통 접두사를 공유하여 압축된 형태로 저장한다. 트리의 높이는 항상 O(n)을 유지한다. 장점 패턴 매칭, 최장 공통 부분 문자열 찾기 등의 연산을 효율적으로 수행한다. 검색 시간이 O(m)으로 매우 빠릅니다(m은 찾는 패턴의 길이). 다양한 문자열 관련 문제를 해결하는 데 활용될 수 있다. 단점 구현이 복잡하고 메모리 사용량이 많다. 구축 비용이 높다. 응용 문자열 검색 및 패턴 매칭 DNA 시퀀싱 및 생물정보학 분석 데이터 압축 알고리즘 텍스트 인덱싱 및 전체 텍스트 검색 동작 원리 문자열의 모든 접미사를 트리에 삽입한다. 공통 접두사를 공유하는 노드를 압축한다. 각 리프 노드에 접미사의 시작 위치를 저장한다. 구성 요소 루트 노드: 트리의 시작점 내부 노드: 공통 접두사를 나타내는 노드 리프 노드: 접미사의 끝을 나타내는 노드 간선: 노드 사이를 연결하며 부분 문자열을 나타냄 구현 방식 Suffix Tree는 일반적으로 Ukkonen’s 알고리즘을 사용하여 선형 시간에 구축할 수 있다. ...