[균형트리] 트리의 종류

등록일 2001.11.29 파워포인트파일MS 파워포인트 (ppt) | 17페이지 | 가격 500원
다운로드
장바구니관심자료
상세신규 배너

목차

균형탐색트리
AVL 트리
AVL 트리에 새로운 노드 삽입
2-3트리
...

본문내용

균형탐색트리
좋은 성능을 유지하려면 트리가 한쪽 방향으로 기울어지지 않도록 해야 한다.

말단 노드에서 루트까지의 높이가 모두 같거나 오직 1만큼만 차이가 난다면
최악의 경우
: 비교 횟수가 log2(n)을 넘지 않는다.


AVL 트리
트리의 높이
단말노드로부터 루트 노드까지의 노드 수 중에 가장 긴 것을 가리킨다.
왼쪽 서브트리와 오른쪽 서브트리의 높이 차이가 1보다 크지 않으면 된다.
AVL트리는 노드가 삽입/삭제될ㅤ때마다 트리가 균형을 이루도록 조정해주어야 한다.
균형치(balance factor)를 부여한다.
( 균형치는 왼쪽 서브트리의 높이에서 오른쪽 서브트리의 높이를 뺀 값이다. )


<균형치가 부여된 AVL트리>


AVL 트리에 새로운 노드 삽입
해당 노드를 삽입하고 균형치를 조정해준다.

균형치가 -1에서 1사이의 값을 가지면 끝낸다.

균형치가 -1보다 작아지거나 1보다 커지면 균형이 깨진 것이다.
(형재 삽입된 노드로부터 가장 가까운 노드에서부터 하위 노드들을 위치를 변형하여 균형을 이루도록 해준다)
2-3트리
  • 구매평가(0)
  • 구매문의(0)
      최근 구매한 회원 학교정보 보기
      1. 최근 2주간 다운받은 회원수와 학교정보이며
         구매한 본인의 구매정보도 함께 표시됩니다.
      2. 매시 정각마다 업데이트 됩니다. (02:00 ~ 21:00)
      3. 구매자의 학교정보가 없는 경우 기타로 표시됩니다.
      4. 지식포인트 보유 시 지식포인트가 차감되며
         미보유 시 아이디당 1일 3회만 제공됩니다.

      찾던 자료가 아닌가요?아래 자료들 중 찾던 자료가 있는지 확인해보세요

      • 파일확장자 AVL트리 (c++) 0페이지
        <자료구조> AVL트리 (c++)
      • 파일확장자 AVL TREE /균형트리 (자료구조, 알고리즘) 0페이지
        , int key) // AVL tree의 삭제 함수 { if( v
      • 한글파일 AVL 트리의 노드 삽입 방법과 C 코드 8페이지
        .) 즉, 균형인수가 ±1인 이진트리AVL트리이다. (밑에 설명에서 N은 ... AVL 트리 *AVL 트리에서의 노드 삽입 방법을 상세히, 알기 쉽게 ... 설명하시오. AVL트리는 항상 균형을 유지하는 이진트리이다. 모든 노드의
      • 파일확장자 화일구조론(파일처리론)_AVL트리, B+트리, Bstar트리, B트리, 이원탐색트리 4페이지
        ..FILE:화일구조론(파일처리론)_AVL트리, B+트리, Bstar ... 트리, B트리, 이원탐색트리/AVL트리.pptx ..PAGE:1 15 15 ... (파일처리론)_AVL트리, B+트리, Bstar트리, B트리, 이원탐색트리
      • 한글파일 2원 탐색트리, AVL트리 레포트 15페이지
        균형시키지 않고도 트리균형 유지 2) 정의 - AVL 트리 T ... REPORT 주제 : 2원 탐색트리, AVL트리 과 목 : 교 수 ... . AVL 트리 3-1 AVL 트리, non-AVL 트리 3-2 AVL
      • 워드파일 AVL 트리의 모든 것 23페이지
        저장하는 AVL 트리의 높이는 O(log n) 3. 자료의 삽입과 균형 ... 있는지 없는지 빨리 알아낼 수 있다. 2. AVL 트리 AVL 트리 ... 균형을 이루는 이진 트리다. 이 균형 트리로 인해 n 개의 노드를 가진
      • 한글파일 AVL 트리와 BB 트리 Splay 트리 6페이지
        AVL 트리의 특성과 유사하다. 두 개의 트리 모두 짧은 탐색 길이와 균형 ... ▷ 이진 탐색 트리균형 트리의 종류 이진 탐색 트리의 성능은 트리 ... Tree ⑵트리균형이 되도록 유지한다. 즉, 각 노드에 대해 왼쪽과
      더보기
      상세하단 배너
      우수 콘텐츠 서비스 품질인증 획득
      최근 본 자료더보기
      [균형트리] 트리의 종류
      페이지
      만족도 조사

      페이지 사용에 불편하신 점이 있으십니까?

      의견 보내기