해피레포트 - [알고리즘 레포트] 234트리,레드블랙트리 조사

카테고리 : 레포트 > 공학,기술계열 파일이름 :[알고리즘 레포트] 234트리,레드블.docx 문서분량 : 11 page 등록인 : leewk2547 문서뷰어 : MS-워드뷰어프로그램 등록/수정일 : 12.05.22 / 12.05.22 구매평가 : 다운로드수 : 0 판매가격 : 2,000 원

미리보기

같은분야 연관자료
재귀알고리즘의 정의와 단점 및 단점극복방법과 사례... 2 pages 2500 원

[e-비즈니스] 1) 암호화 알고리즘 중 PKI라고 불리는 공개키 방식 알고리즘 2) 암호화 ... 10 pages 5000 원

[공학]유전알고리즘을 이용한 도로표지판 지주의 최적설계... 6 pages 2000 원

엘레베이터 알고리즘과 효율성 제고... 6 pages 2000 원

[정보보호론] DES알고리즘에 대해... 14 pages 2000 원

보고서설명
Tree를 이용하는 binary search는 complete binary 트리의 경우 O(nlog n) 이라는 실용적인 탐색시간을 보장한다. 하지만 실제 세계에서는 데이터의 입력이 항상 complete binary tree를 만드는 것을 보장해 주지는 않는다. 따라서 최악의 경우에는 O(n*n)이라는 사태가 발생할 수도 있는 것이다. 이런 worst case를 막기 위해서 data를 insertion하는 방법에 있어서 많은 방법들이 등장하였지만, 좀 더 근본적인 부분에서 해결을 하기 위해 자료구조 자체에 대한 연구가 이루어졌고, 그에 대한 결과물 중의 하나가 바로 2-3-4트리이다.

본문일부/목차
1. 키를 삽입해야 하는 노드가 2-노드 또는 3-노드인 단말 노드일 경우 별도의 연산 과정 없이 키값에 해당하는 위치에 삽입한다. 2. 키를 삽입해야 하는 단말 노드가 4-노드인 경우, 키값을 삽입하게 되면 단말 노드에 키값이 4개가 들어가게 되어 노드가 5개가 되는 Overflow 현상이 발생하게 된다. 이 때 2-3-4 tree의 성질을 유지시켜 주기 위해서 별도의 연산이 필요해지게 되는데 이 연산을 split 연산이라고 부른다. 또한, split 연산은 overflow를 발생시키는 인자, 즉 한계를 넘어서 키를 부모 노드로 넘겨주는 방식으로 overflow를 해결하기 때문에 overflow가 부모 노드로 계속해서 전달되는 backward가 발생할 수 있다. 이것을 해결하기 위해서는 두 가지의 방법이 있다. split연산을 수행한 노드의 부모 노드에 대해서 다시 split연산을 수행하여 루트까지 체크를 하거나, 개요 부분에서 제시한 바와 같이 루트에서 키 값을 탐색하면서 내려올 때 4개의 자식 노드를 가진(3개의 키값을 가진) 모든 노드를 미리 split연산을 수행하는 것이다. 이렇게 할 경우, 단말 노드에서의 split연산이 backward를 불러일으키지 않을 것을 보장할 수 있다. 3. 4-노드의 위치에 따른 분할 케이스들 ∙ 4-노드가 2-3-4 트리의 루트인 경우 ∙ 4-노드가 2-노드의 자식인 경우 왼쪽자식, 왼쪽 중간 자식 ∙ 4-노드가 3-노드의 자식인 경우 왼쪽자식, 왼쪽 중간 자식, 오른쪽 자식

연관검색어
알고리즘

구매평가

구매평가 기록이 없습니다

보상규정 및 환불정책
· 해피레포트는 다운로드 받은 파일에 문제가 있을 경우(손상된 파일/설명과 다른자료/중복자료 등) 1주일이내 환불요청 시
환불(재충전) 해드립니다. (단, 단순 변심 및 실수로 인한 환불은 되지 않습니다.)
· 파일이 열리지 않거나 브라우저 오류로 인해 다운이 되지 않으면 고객센터로 문의바랍니다.
· 다운로드 받은 파일은 참고자료로 이용하셔야 하며,자료의 활용에 대한 모든 책임은 다운로드 받은 회원님에게 있습니다.

저작권안내

카테고리 : 레포트 > 공학,기술계열
파일이름 :[알고리즘 레포트] 234트리,레드블.docx
문서분량 : 11 page	등록인 : leewk2547
문서뷰어 : MS-워드뷰어프로그램	등록/수정일 : 12.05.22 / 12.05.22
구매평가 :	다운로드수 : 0

[알고리즘 레포트] 234트리,레드블랙트리 조사

판매가격 : 2,000 원