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