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

통합검색

레포트

방송통신

서식

5페이지 미만은 미리보기가
제공되지 않습니다.
공학,기술계열 알고리즘 AVL Tree(AVL 트리) AVL트리(09).hwp 등록인 colroki 등록/수정일 12.11.18 / 12.11.18 문서분량 4 페이지 다운로드 2 구매평가 판매가격 1,500원

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

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

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

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

[정보보호론] DES알고리즘에 대해... 14 페이지 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주일이내 환불요청 시 환불(재충전) 해드립니다. (단, 단순 변심 및 실수로 인한 환불은 되지 않습니다.) · 파일이 열리지 않거나 브라우저 오류로 인해 다운이 되지 않으면 고객센터로 문의바랍니다. · 다운로드 받은 파일은 참고자료로 이용하셔야 하며,자료의 활용에 대한 모든 책임은 다운로드 받은 회원님에게 있습니다.

저작권안내

저작권침해신고 바로가기

미리보기는 3페이지까지
제공 됩니다.

5페이지 미만은 미리보기가
제공 되지않습니다.

알고리즘 AVL Tree(AVL 트리)

판매가격 1,500원