[알고리즘 리포트] 234트리,레드블랙트리 조사
페이지 정보
작성일 23-04-15 09:40
본문
Download : [알고리즘 레포트] 234트리,레드블.docx
다.
4개가 들어가게 되어 노드가 5개가 되는 Overflow 현상이 발생하게 된다된다. 따라서 최악의 경우에는 O(n*n)이라는 사태가 발생할 수도 있는 것이다. 따라서 최악의 경우에는 O(n*n)이라는 사태가 발생할 수도 있는 것이다.
2. 키를 삽입해야 하는 단말 노드가 4-노드인 경우, 키값을 삽입하게 되면 단말 노드에 키값이
레포트 > 공학,기술계열
왼쪽자식, 왼쪽 중간 자식
![[알고리즘 레포트] 234트리,레드블-2011_01.gif](https://sales.happyreport.co.kr/prev/201205/%5B%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98%20%EB%A0%88%ED%8F%AC%ED%8A%B8%5D%20234%ED%8A%B8%EB%A6%AC,%EB%A0%88%EB%93%9C%EB%B8%94-2011_01.gif)
![[알고리즘 레포트] 234트리,레드블-2011_02_.gif](https://sales.happyreport.co.kr/prev/201205/%5B%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98%20%EB%A0%88%ED%8F%AC%ED%8A%B8%5D%20234%ED%8A%B8%EB%A6%AC,%EB%A0%88%EB%93%9C%EB%B8%94-2011_02_.gif)
![[알고리즘 레포트] 234트리,레드블-2011_03_.gif](https://sales.happyreport.co.kr/prev/201205/%5B%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98%20%EB%A0%88%ED%8F%AC%ED%8A%B8%5D%20234%ED%8A%B8%EB%A6%AC,%EB%A0%88%EB%93%9C%EB%B8%94-2011_03_.gif)
![[알고리즘 레포트] 234트리,레드블-2011_04_.gif](https://sales.happyreport.co.kr/prev/201205/%5B%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98%20%EB%A0%88%ED%8F%AC%ED%8A%B8%5D%20234%ED%8A%B8%EB%A6%AC,%EB%A0%88%EB%93%9C%EB%B8%94-2011_04_.gif)
![[알고리즘 레포트] 234트리,레드블-2011_05_.gif](https://sales.happyreport.co.kr/prev/201205/%5B%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98%20%EB%A0%88%ED%8F%AC%ED%8A%B8%5D%20234%ED%8A%B8%EB%A6%AC,%EB%A0%88%EB%93%9C%EB%B8%94-2011_05_.gif)
왼쪽자식, 왼쪽 중간 자식, 오른쪽 자식
또한, split 연산은 overflow를 발생시키는 인자, 즉 한계를 넘어서 키를 부모 노드로 넘겨주는 방식으로 overflow를 해결하기 때문에 overflow가 부모 노드로 계속해서 전달되는 backward가 발생할 수 있다아 이것을 해결하기 위해서는 두 가지의 방법이 있다아 split연산을 수행한 노드의 부모 노드에 상대하여 다시 split연산을 수행하여 루트까지 체크를 하거나, 개요 부분에서 제시한 바와 같이 루트에서 키 값을 탐색하면서 내려올 때 4개의 자식 노드를 가진(3개의 키값을 가진) 모든 노드를 미리 split연산을 수행하는 것이다. 하지만 실제 세계에서는 데이터의 입력이 항상 complete binary tree를 만드는 것을 보장해 주지는 않는다. 이 때 2-3-4 tree의 성질을 유지시켜 주기 위해서 별도의 연산이 필요해지게 되는데 이 연산을 split 연산이라고 부른다. 이런 worst case를 막기 위해서 data를 insertion하는 방법에 있어서 많은 방법들이 등장하였지만, 좀 더 근본적인 부분에서 해결을 하기 위해 data(資料)구조 자체에 대한 연구가 이루어졌고, 그에 대한 결과물 중의 하나가 바로 2-3-4트리이다.
Tree를 이용하는 binary search는 complete binary 트리의 경우 O(nlog n) 이라는 실용적인 탐색시간을 보장한다. 하지만 실제 세계에서는 데이터의 입력이 항상 complete binary tree를 만드는 것을 보장해 주지는 않는다. 이렇게 할 경우, 단말 노드에서의 split연산이 backward를 불러일으키지 않을 것을 보장할 수 있다아
순서
알고리즘,234트리,레드블랙트리
∙ 4-노드가 3-노드의 자식인 경우
∙ 4-노드가 2-노드의 자식인 경우
∙ 4-노드가 2-3-4 트리의 루트인 경우
3. 4-노드의 위치에 따른 분할 케이스들
설명
Download : [알고리즘 레포트] 234트리,레드블.docx( 18 )
1. 키를 삽입해야 하는 노드가 2-노드 또는 3-노드인 단말 노드일 경우 별도의 연산 과정 없이 키값에 해당하는 위치에 삽입한다.
[알고리즘 리포트] 234트리,레드블랙트리 조사
Tree를 이용하는 binary search는 complete binary 트리의 경우 O(nlog n) 이라는 실용적인 탐색시간을 보장한다. 이런 worst case를 막기 위해서 data를 insertion하는 방법에 있어서 많은 방법들이 등장하였지만, 좀 더 근본적인 부분에서 해결을 하기 위해 자료구조 자체에 대한 연구가 이루어졌고, 그에 대한 결과물 중의 하나가 바로 2-3-4트리이다.
