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
      최근 구매한 회원 학교정보 보기
      1. 최근 2주간 다운받은 회원수와 학교정보이며
         구매한 본인의 구매정보도 함께 표시됩니다.
      2. 매시 정각마다 업데이트 됩니다. (02:00 ~ 21:00)
      3. 구매자의 학교정보가 없는 경우 기타로 표시됩니다.
      최근 본 자료더보기
      추천도서