처음으로 | 찾기 | 아카이브 | 글 올리기 | 링크 | 자료실 | 통계 | 연락처 | 자유게시판
이지도움 특집
TI DaVinci
Analog Blackfin
캐쉬의 모든것
메모리 할당 알고리즘
CPU 파이프라이닝




사용자 등록

현재 접속중인 등록 사용자는 0명, 익명 사용자는 2명 입니다.
전체 등록 사용자: 751명

마지막 답장
·libcurl + fuse 조합으로 되는게 많네. (1)
·Linux Ftrace에 관해 (3)
·Android MTP ( Media Transfer Protocol ) (1)
·Lighttpd에 인증을 digest 사용시 IE 오동작 문제? (1)
·Dtrace에 관해 (1)

·OpenSSL and multi-threads (0)
·ARM 환경에서 OpenCL 사용 (0)
·IoT용 WIFI 모듈 비교 ( MCU ) 클래스 (0)
·Glances - 리눅스 여러 가지 항목을 한 화면에서 모니터링 (0)
·plugin 방식의 로그 분석기 (0)

뜨거운 감자
·나는 인터렉티브한 환경에서 역어셈블 한다. (12)
·GNU REGEX (정규표현식) 프로그래밍 강좌 (7)
·SoCRobotWar 2005 - 신입생 기초 교육자료 (7)
·ASP.NET의 데이터 그리드와 사용자 컨트롤 (7)
·DHTML Editing Control (7)

가장 많이 읽은 글
·[Cache] 2-way Set-Associative 방식이란 무엇일까? (2)
·멀티쓰레드(Pthread) 프로그래밍
·GNU REGEX (정규표현식) 프로그래밍 강좌 (7)
·Sorting Algorithm Animation (2)
·SoCRobotWar 2005 - 신입생 기초 교육자료 (7)

Tree Rebalancing in Optimal Time and Space
글쓴이: EzDoum 글쓴날: 2002년 06월 26일 오후 10:51

In Communications of the ACM 29 (1986), pp. 902-908.
Tree Rebalancing in Optimal Time and Space

Quentin F. Stout
EECS Department, University of Michigan

Bette L. Warren
Mathematics Department, Eastern Michigan University

Abstract: A simple algorithm is given which takes an arbitrary binary search tree and rebalances it to form another of optimal shape, i.e., not only does the resulting tree have minimal possible height, but further, for each node, the number of nodes in its left and right subtrees differ by at most one. This algorithm uses time linear in the number of nodes and only a constant amount of space beyond that used to store the initial tree. It is thus optimal in its use of both time and space. Previous algorithms were optimal in at most one of these two measures, or were not applicable to all binary search trees.

When the nodes are stored in an array, a simple addition to this algorithm results in the nodes being stored in sorted order in the initial portion of the array, again using only linear time and constant space.

The algorithm consists of two phases:

tree_to_vine, which converts an arbitrary binary search tree into a vine, where the smallest item is the root, next smallest item is to its right, etc.
vine_to_tree, which converts the vine into a perfectly balanced tree.
The phases are based on repeated use of simple rotation operations. Each phase is quite efficient, and is of interest in itself.
While not included in this paper, it is also straightforward to modify the algorithm so that the result is a red-black, AVL, or weight-balanced tree (and many other variations as well). I.e., the node information needed for these trees is inserted during the vine_to_tree step.

Keywords: global binary search tree rebalance, data structure, perfect balance, optimal search, sorting, algorithm, vine, rebalance, minimal height, rotation, computer science

The Association for Computing Machinery (ACM) has scanned this journal and put it online. Here is their PDF version of this paper.

  • 첨부 파일: TreeRebalancinginOptimalTimeandSpace.pdf TreeRebalancinginOptimalTimeandSpace.pdf (612 KiB(626,902 Bytes))

  • 관련 링크
  • [분류: C/C++ 인쇄용 페이지 본문 email로 보내기 ]

    <  트리 발전사라고 해야 하나 ^^? | GNU libavl  >

    답장 쓰기
    글을 올리시려면 로그인 (사용자 등록) 하셔야 합니다.


    ·공지 (6)
    ·인터넷 (87)
    ·하드웨어 (260)
    ·C/C++ (65)
    ·어셈블리 (7)
    ·리눅스 (136)
    ·리눅스 커널 (67)
    ·윈도우즈 (25)
    ·데이터베이스 (20)
    ·보안 (16)
    ·.NET (25)
    ·그래픽 (13)
    ·책소개 (42)
    ·호기심 천국 (80)
    ·잡담 (111)
    ·사랑 (3)

    전체 본문수: 963
    전체 답장수: 525

    분류 : C/C++
    가장 많이 읽은 글
    ·Sorting Algorithm Animation (2)
    뜨거운 감자
    ·눈으로 보는 자료구조 (5)

    이지도움 어때요?
    이게 뭐야. 다시 안올란다. --;
    아이 좋아라~ +_+;
    먼가는 있는거 같은데 뭐하는 곳이지?
    기타 (자유게시판에 글로 남겨 주세요)
    [ 결과 | 투표 ]

    랜덤 링크

     Home ^ BACK TO TOP ^ EzDoum - 도움이 필요하세요~??
     Powered by KorWeblog 1.5.8 Copyleft © 2001 EzDoum, 관리자: EzDoum