해피레포트 - 알고리즘 AVL Tree(AVL 트리)

카테고리 : 레포트 > 공학,기술계열 파일이름 :AVL트리(09).hwp 문서분량 : 4 page 등록인 : colroki 문서뷰어 : 한글뷰어프로그램 등록/수정일 : 12.11.18 / 12.11.18 구매평가 : 다운로드수 : 2 판매가격 : 1,500 원

미리보기

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

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

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

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

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

보고서설명
알고리즘 AVL Tree(AVL 트리)

본문일부/목차
1. AVL-Tree 란? 2. AVL-Tree가 나온 배경 3. AVL-Tree의 특징 4. AVL-Tree의 핵심 5. AVL-Tree의 삽입 코드 1. AVL-Tree 란? 좌, 우측 부트리의 높이가 1이상 차이가 나지 않도록 균형을 유지한 트리로 결국은 탐색시간을 줄일 수 있고, 노드 삽입시 트리의 균형이 크게 변하지 않는 성질을 지닌다. 2. AVL-Tree가 나온 배경 바이너리 트리가 단점을 지니고 있다고 한다면 그것은 노드의 깊이가 불균형해질 수 있다는 점으로 최악의 경우에 O(n)의 시간을 소비할 수도 있다. 이러한 이유 때문에 트리의 균형을 맞추고자하는 시도가 시행되었고 그 결과 AVL-Tree는 최초로 고안해낸 균형 트리가 되었다. 3. AVL-Tree의 특징 AVL은 항상 height를 O(logn)으로 유지한다. 1. N(h)는 높이가 h인 AVL에 존재할 수 있는 최소 노드의 개수이다. 2. N(0) = 1, N(1) = 2 3. N(h) = N(h-1)+N(h-2)+1 이므로 아래의 공식이 성립 4. 그러므로 h=log_1.618^n=O(logn)이 됨 4. AVL-Tree의 핵심 트리가 나온 배경을 보면 알 수 있듯이 균형을 맞추기 위한 방법이 중요하다고 할 수 있다. 일반적인 트리의 균형에 대한 문제는 새로운 노드의 추가 시에 발생을 하게 된다. 높이 균형 트리를 구성하는데 있어서 각 노드에 그 노드의 좌측, 우측 부트리 사이의 높이차를 나타내는 균형 인수(Balance Factor:BF)를 두어 어떠한 노드에 대해서도 BF는 -1, 0, +1 중의 한 개의 값을 취하게 된다. 이것은 즉 모든 노드의 균형 인수가 ±1 이하이면 AVL-Tree라는 뜻이 된다. &⦁균형 인수(Balance Factor) = (왼쪽 서브 트리의 높이-오른쪽 서브 트리의 높이) 만약에 BF가 +2나 -2가 된다고 하면 더 이상 진행이 되지 않고 아래와 같은 4가지 회전을 통해서 균형을 맞도록 유지시킨다. 새로 삽입된 노드를 N, 그리고 N으로부터 가장 가까운 조상 노드를 A라고 하자.

연관검색어
알고리즘

구매평가

구매평가 기록이 없습니다

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

저작권안내

카테고리 : 레포트 > 공학,기술계열
파일이름 :AVL트리(09).hwp
문서분량 : 4 page	등록인 : colroki
문서뷰어 : 한글뷰어프로그램	등록/수정일 : 12.11.18 / 12.11.18
구매평가 :	다운로드수 : 2

알고리즘 AVL Tree(AVL 트리)

판매가격 : 1,500 원