AVL 트리와 BB 트리 Splay 트리

등록일 2003.05.28 한글 (hwp) | 6페이지 | 가격 500원

목차

▷ 이진 탐색 트리의 균형
1.AVL 트리
2.BB(Bounded - balanced) 트리
3. Splay 트리

본문내용

3. Splay 트리
Sleator와 Tarjan에 의해 제안된 것으로 스플레이 트리는 최근에 접근되었던 노드 x를 루트에 오려놓기 위해, 연속된 회전으로 정의되는 스플레이를 노드 x에 적용시킨다.
탐색, 삽입, 삭제는 항상 성공적이라고 가정하자. 실패는 다른 성공적인 연산으로 모델화할 수 있다. 예를 들어 성공하지 못한 탐색의 경우 성공하지 못한 탐색시 마지막으로 방문한 노드내의 원소에 대한 탐색으로 모델화하고, 성공하지 못한 삽입은 성공적인 탐색으로 모델화할 수 있다. 이러한 가정하에서 스플레이를 위한 시작 노드는 다음과 같이 얻을 수 있다.

참고 자료

C로 쓴 자료구조, 이석호 역, 사이텍미디어, 1993
*원하는 자료를 검색 해 보세요.
  • [균형트리] 트리의 종류 17페이지
    균형탐색트리 좋은 성능을 유지하려면 트리가 한쪽 방향으로 기울어지지 않도록 해야 한다. 말단 노드에서 루트까지의 높이가 모두 같거나 오직 1만큼만 차이가 난다면 최악의 경우 : 비교 횟수가 log2(n)을 넘지 않는다. AVL 트리 트리의 높이 단말노드로부터 루트 노드..
  • [자료구조론]트리(Tree) 15페이지
    ◈ 트리(tree) ◆ 트리의 정의 - 대상 정보를 계층적으로 구조화시키고자 할 때 사용하는 자료구조가 "트리" 이다. (자료 사이의 계층적 관계를 구조화) 위의 혈통도는 "가계"라는 대상 정보를 단순히 데이터 요소를 나열하여 표현하지 않고, 데이터 요소들 간의 "pa..
  • [공학]트리에 관해서 4페이지
    1. B트리 (1)B-트리 인덱스를 조직하는 방법으로 가장 많이 사용되는 구조는 B-트리이다. B-트리는 균형된 m-원 트리로서 효율적인 균형알고리즘을 제공한다. 차수가 m인 B-트리는 다음과 같은 특성을 가진 m-원 탐색 트리로 정의할수 있다. ① 루트와 리프를 제외..
  • 알고리즘트리_01 11페이지
    REPORT (트리-이진트리) Contents ?서론 Ⅰ. 트리의 정의 Ⅱ. 트리의 조건 Ⅲ. 트리의 용어 설명 ?본론 Ⅳ. 트리의 종류 1. 자유 트리 2. 순서 트리와 비순서 트리 3. 닮은 트리와 대등트리 4. 이진 트리 1) 이진 트리 정의 2) 이진 트리의 ..
  • 트리에대하여 29페이지
  • [자료구조] 자료구조(일반트리와 이진트리) 18페이지
    트리의 개요 (1) 정의 · 트리는 연결된 비순환 그래프의 일종이다(비선형 구조).· 트리 구조는 나무나 족보에서 보는 것처럼 노드 사이의 관계가 계급적 관련성을 갖는다.· 트리는 정점에서의 가지수에 따라 이진 트리와 m-원 트리로 나뉜다.
  • R트리,R+트리,R*트리 4페이지
    R-트리 1. R-트리의 개념 ① B-트리를 다차원 구조로 확장 ② 디스크 페이지 단위로 데이터를 저장, 검색할 수 있어서 대용량 데이터에 대한 인덱스 구조로 적당 ③ 인덱스 구조는 B-트리와 같이 높이 균형 트리(height balanced tree) ④ 리프 노드..
더보기
      최근 구매한 회원 학교정보 보기
      1. 최근 2주간 다운받은 회원수와 학교정보이며
         구매한 본인의 구매정보도 함께 표시됩니다.
      2. 매시 정각마다 업데이트 됩니다. (02:00 ~ 21:00)
      3. 구매자의 학교정보가 없는 경우 기타로 표시됩니다.
      4. 지식포인트 보유 시 지식포인트가 차감되며
         미보유 시 아이디당 1일 3회만 제공됩니다.
      상세하단 배너
      최근 본 자료더보기
      상세우측 배너
      추천도서
      AVL 트리와 BB 트리 Splay 트리