위키원
"스큐드 머클트리"의 두 판 사이의 차이
(→개요: 내용을 수정함) (태그: 모바일 편집, 모바일 웹 편집) |
(→개요: 목차 추가함) (태그: 모바일 편집, 모바일 웹 편집) |
||
| 3번째 줄: | 3번째 줄: | ||
==개요== | ==개요== | ||
이진 탐색 트리의 탐색 연산은 O(log n)의 시간 복잡도를 갖는다. 트리의 높이를 하나씩 더해갈수록 추가할 수 있는 노드의 수가 두 배씩 증가하기 때문이다. 하지만 저장 순서에 따라 계속 한 쪽으로만 노드가 추가되는 경우가 발생할 수 있는데, 이러한 경우에 스큐드 머클트리가 된다. 이럴 경우 성능에 영향을 미치게 되며, 탐색의 Worst Case가 되고 시간 복잡도는 0(n)이 된다. | 이진 탐색 트리의 탐색 연산은 O(log n)의 시간 복잡도를 갖는다. 트리의 높이를 하나씩 더해갈수록 추가할 수 있는 노드의 수가 두 배씩 증가하기 때문이다. 하지만 저장 순서에 따라 계속 한 쪽으로만 노드가 추가되는 경우가 발생할 수 있는데, 이러한 경우에 스큐드 머클트리가 된다. 이럴 경우 성능에 영향을 미치게 되며, 탐색의 Worst Case가 되고 시간 복잡도는 0(n)이 된다. | ||
| + | |||
| + | ==리밸런싱 기법== | ||
{{각주}} | {{각주}} | ||
2019년 9월 5일 (목) 13:47 판
스큐드 머클트리(skewed merkle)란 머클 트리 중에서 최소 개수의 노드를 가지면서, 왼쪽이나 오른쪽 서브 트리만 가지고 있는 트리이다. 머클트리(merkle tree)는 해시트리(hash tree), 이진트리(binary tree)라고도 불리기 때문에 스큐드 머클트리는 사향 이진트리(skewed binary tree), 편향 이진트리라고도 불리기도 한다.
개요
이진 탐색 트리의 탐색 연산은 O(log n)의 시간 복잡도를 갖는다. 트리의 높이를 하나씩 더해갈수록 추가할 수 있는 노드의 수가 두 배씩 증가하기 때문이다. 하지만 저장 순서에 따라 계속 한 쪽으로만 노드가 추가되는 경우가 발생할 수 있는데, 이러한 경우에 스큐드 머클트리가 된다. 이럴 경우 성능에 영향을 미치게 되며, 탐색의 Worst Case가 되고 시간 복잡도는 0(n)이 된다.
리밸런싱 기법
각주
참고자료
- 푸른하늘의해, 〈이진 트리(Binary Tree)〉, 《네이버 블로그》, 2012-07-08
- _lbee, 〈(DataStructure) 5. Red-Black Tree〉, 《티스토리》, 2017-03-11
