SB tree （Size Balanced Tree）

전송:http://www.clarkok.com/blog/?p=347#more-347
네티즌 의 조언 을 받 아 SB Tree 를 써 보 세 요.
============================================================================
SB 란 바보 X 가 아니 라 Size Balanced 라 는 뜻 이다.본인 도 비교적 사용 을 건의 합 니 다. 쓰기 가 비교적 간단 하기 때 문 입 니 다.이런 나무 구 조 는 하나의 특징 이 있 는데 모든 노드 에 대해 그의 좌우 나무 크기 (단순히 노드 수량 으로 이해 할 수 있 음) 가 같 거나 하나만 다르다.
정의 및 초기 화

type
    point       = ^node;
    node        = record
        l,r     : point;
        x,s     : longint;
    end;

var
    root,null   : point;
    tmp         : point;

procedure init;
begin
    new(null);
    null^.x:=-maxlongint;
    null^.s:=0;
    null^.l:=null;
    null^.r:=null;

    root:=null;
end;

이것 은 다른 몇 가지 나무 와 구조 차이 가 많 지 않 습 니 다. 변수 s (size) 를 하나 더 유지 하고 이 노드 를 뿌리 로 하 는 하위 나무의 크기 를 저장 합 니 다.분명히 빈 나무의 크기 는 0 이다.
끼어들다
PS. 회전 에 관 해 서 는 AVL 트 리 를 참조 하 세 요.
삽입 은 매우 간단 합 니 다. 먼저 노드 를 정확 한 위치 에 꽂 은 다음 에 재 귀 할 때 회전 을 통 해 나무의 크기 를 조정 합 니 다.그림:
이 나무 에 1 삽입:
대응 하 는 위치 에 삽입:
회전 한 후에 (여 기 는 5 만 회전 합 니 다. 2, 3 노드 가 모두 요 구 를 만족 시 키 기 때 문 입 니 다):
우 리 는 여전히 함수 로 쓴다.

function add(now:point;x:longint):point;
begin
    if now = null then                               //        
        begin
            new(now);
            now^.l:=null;
            now^.r:=null;
            now^.s:=1;
            now^.x:=x;
            exit(now);
        end;
    if now^.x >x then
        begin
            now^.l:=add(now^.l,x);
            inc(now^.s);
            if now^.l^.s > now^.r^.s+1 then          //     
                begin
                    now^.s:=now^.r^.s+now^.l^.r^.s+1;
                    now^.l^.s:=now^.s+now^.l^.l^.s+1;
                    exit(TurnLeft(now));
                end;
            exit(now);
        end
    else
        begin
            now^.r:=add(now^.r,x);
            inc(now^.s);
            if now^.r^.s > now^.l^.s+1 then
                begin
                    now^.s:=now^.l^.s+now^.r^.l^.s+1;
                    now^.r^.s:=now^.s+now^.r^.r^.s+1;
                    exit(TurnRight(now));
                end;
            exit(now);
        end;
end;

삭제
AVL 과 같은 생각 으로 잎 사 귀 로 돌려 서 지우 고, Size 가 큰 하위 트 리 로 돌려 줍 니 다.사 는 게 뭔 지도 AVL 참조 하 세 요.

function del(now:point;x:longint):point;
begin
    if now = null then
        exit(null);
    if now^.x = x then
        if now^.l^.s > now^.r^.s then
            begin
                now:=TurnLeft(now);
                now^.r:=del(now^.r,x);
                dec(now^.s);
            end
        else
            begin
                if now^.r = null then
                    begin
                        dispose(now);
                        exit(null);
                    end;
                now:=TurnRight(now);
                now^.l:=del(now^.l,x);
                dec(now^.s);
            end
    else
        if now^.x > x then
            now^.l:=del(now^.l,x)
        else
            now^.r:=del(now^.r,x);
    dec(now^.s);
    exit(now);
end;