[균형트리] 트리의 종류

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