[균형트리] 트리의 종류

등록일 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트리
*원하는 자료를 검색 해 보세요.
  • [공학]트리에 관해서 4페이지
    1. B트리 (1)B-트리 인덱스를 조직하는 방법으로 가장 많이 사용되는 구조는 B-트리이다. B-트리는 균형된 m-원 트리로서 효율적인 균형알고리즘을 제공한다. 차수가 m인 B-트리는 다음과 같은 특성을 가진 m-원 탐색 트리로 정의할수 있다. ① 루트와 리프를 제외..
  • [자료구조론]트리(Tree) 15페이지
    ◈ 트리(tree) ◆ 트리의 정의 - 대상 정보를 계층적으로 구조화시키고자 할 때 사용하는 자료구조가 "트리" 이다. (자료 사이의 계층적 관계를 구조화) 위의 혈통도는 "가계"라는 대상 정보를 단순히 데이터 요소를 나열하여 표현하지 않고, 데이터 요소들 간의 "pa..
  • R트리,R+트리,R*트리 4페이지
    R-트리 1. R-트리의 개념 ① B-트리를 다차원 구조로 확장 ② 디스크 페이지 단위로 데이터를 저장, 검색할 수 있어서 대용량 데이터에 대한 인덱스 구조로 적당 ③ 인덱스 구조는 B-트리와 같이 높이 균형 트리(height balanced tree) ④ 리프 노드..
  • [자료구조] 자료구조(일반트리와 이진트리) 18페이지
    트리의 개요 (1) 정의 · 트리는 연결된 비순환 그래프의 일종이다(비선형 구조).· 트리 구조는 나무나 족보에서 보는 것처럼 노드 사이의 관계가 계급적 관련성을 갖는다.· 트리는 정점에서의 가지수에 따라 이진 트리와 m-원 트리로 나뉜다.
  • 이진 탐색트리 20페이지
    8장 이진탐색트리 이진 탐색 트리(1) 특징 임의의 키를 가진 원소를 삽입, 삭제, 검색하는데 효율적인 자료구조 모든 연산은 모두 키값을 기초로 실행 정의: 이진 탐색 트리(binary search tree:BST) 이진 트리 공백이 아니면 다음 성질을 만족 모든 원소..
  • 알고리즘트리_01 11페이지
    REPORT (트리-이진트리) Contents ?서론 Ⅰ. 트리의 정의 Ⅱ. 트리의 조건 Ⅲ. 트리의 용어 설명 ?본론 Ⅳ. 트리의 종류 1. 자유 트리 2. 순서 트리와 비순서 트리 3. 닮은 트리와 대등트리 4. 이진 트리 1) 이진 트리 정의 2) 이진 트리의 ..
  • 트리 51페이지
    제 5 장 트리 - 제 5장. 트리 5.1 서론 --------------------------------------------------------------------------------------------------- ▶ 트리 트리 : 하나이상의 노드(node..
더보기
      최근 구매한 회원 학교정보 보기
      1. 최근 2주간 다운받은 회원수와 학교정보이며
         구매한 본인의 구매정보도 함께 표시됩니다.
      2. 매시 정각마다 업데이트 됩니다. (02:00 ~ 21:00)
      3. 구매자의 학교정보가 없는 경우 기타로 표시됩니다.
      4. 지식포인트 보유 시 지식포인트가 차감되며
         미보유 시 아이디당 1일 3회만 제공됩니다.
      상세하단 배너
      최근 본 자료더보기
      상세우측 배너
      추천도서
      [균형트리] 트리의 종류