[균형트리] 트리의 종류

등록일 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트리
*원하는 자료를 검색 해 보세요.
  • 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 Tree(AVL 트리) 4페이지
    균형 트리가 되었다. 3. AVL-Tree의 특징 AVL은 항상 ... -Tree 삽입 연산후의 AVL-Tree 회전으로 균형 트리를 만듦 5 ... 1이상 차이가 나지 않도록 균형을 유지한 트리로 결국은 탐색시간을 줄일
  • AVL 트리와 BB 트리 Splay 트리 6페이지
    AVL 트리의 특성과 유사하다. 두 개의 트리 모두 짧은 탐색 길이와 균형 ... ▷ 이진 탐색 트리균형 트리의 종류 이진 탐색 트리의 성능은 트리 ... Tree ⑵트리균형이 되도록 유지한다. 즉, 각 노드에 대해 왼쪽과
  • [자료구조]AVL트리 0페이지
    , char* s, Bool* h) { //AVL트리 구성함수 node ... * current) { //AVL트리 문자열과 카운터 함수 if ... 1(node* current) { //AVL트리 알파벳순 출력함수 if
  • avl트리 정렬 0페이지
    1. 입력 화일로부터 정수들을 읽어들여 AVL트리를 생성하고 생성된 ... AVL 트리가 생김을 알 수 있다. 4 / | 2 6 /| /| 1 3 5 ... , tree_node x); //AVL트리를 출력함 void sort
  • [알고리즘] avl트리 5페이지
    실제 AVL트리를 형상화 했을때의 높이를 말하고 height는 프로그램 ... _ptr; /* 트리 구성 */ typedef struct tree_node ... the following: - AVL Tree
더보기
      최근 구매한 회원 학교정보 보기
      1. 최근 2주간 다운받은 회원수와 학교정보이며
         구매한 본인의 구매정보도 함께 표시됩니다.
      2. 매시 정각마다 업데이트 됩니다. (02:00 ~ 21:00)
      3. 구매자의 학교정보가 없는 경우 기타로 표시됩니다.
      4. 지식포인트 보유 시 지식포인트가 차감되며
         미보유 시 아이디당 1일 3회만 제공됩니다.
      상세하단 배너
      최근 본 자료더보기
      상세우측 배너
      추천도서
      [균형트리] 트리의 종류