assume cs:code,ds:data,ss:stack
data segment
;存储B树
;关键字个数,父指针,关键字数组,儿子指针数组,
BTRD db 256 dup(0)
;构建树的原始数据
NODED db 45,24,3,12,37,53,90,50,61,70,99,'#'
;根指针
BOOT db 0
;节点数量
NODENUM db 0
SIGN db 8
TEMP dw 0,0
;变量
BTRV db 16 dup(0)
RIGHT db "Copyright (c) 2007 www.asmedu.net#"
data ends
stack segment stack
dw 32 dup(0)
stack ends
code segment
start:
mov ax,data
mov ds,ax
mov si,0
mov ax,stack
mov ss,ax
mov sp,0
mov byte ptr NODENUM[0],0
mov byte ptr BOOT[0],-1
call CreateTree
mov byte ptr BTRV[0],68
call InsertNode
mov byte ptr BTRV[0],12
call SearchNode
mov byte ptr BTRV[0],3
call DelBNode
mov ax,4c00h
int 21h
;-----------------------------------CreateTree start
;根据ds:[si]的数据位置创建一棵3阶B树
;这里把阶定义为非根节点中子树的最大数目。
CreateTree:
push ax
push si
mov si,0
CBTS:
cmp byte ptr NODED[si],'#'
je CBTRe
mov al,NODED[si]
mov BTRV[0],al
call InsertNode
inc si
jmp CBTS
CBTRe:
pop si
pop ax
ret
;-----------------------------------CreateTree end
;-----------------------------------SearchNode start
;前序遍历在B树中查找关键字
;BTRV[0]存储要查找的关键字
;BTRV[1]返回值 1不存在树,2不存在关键字
;找到返回BTRV[1]节点的位置,BTRV[2]关键字在节点中的位置
SearchNode:
push ax
push bx
push cx
push dx
push di
push si
mov bx,0
mov bl,BOOT[0]
;是否存在树
cmp byte ptr BOOT[0],-1
jne SNS
;未找到
mov byte ptr BTRV[1],1
jmp SNReturn
;查找当前节点是否有关键字
SNS:
mov byte ptr BTRD[bx + 2],0
mov cx,0
mov cl,BTRD[bx]
mov di,0
mov al,BTRV[0]
SNS1:
cmp BTRD[bx + di + 3],al
je SNS2
inc di
loop SNS1
jmp SNS3
SNS2:
;找到返回
mov BTRV[1],bl
mov ax,di
mov BTRV[2],al
jmp SNReturn
;当前节点是底层节点?
SNS3:
cmp byte ptr BTRD[bx + 6],-1
je SNS4
inc byte ptr BTRD[bx + 2]
mov ax,0
mov al,BTRD[bx + 6]
mov bx,ax
jmp SNS
;返回到父节点,父节点是否还有未访问的孩子
SNS4:
cmp byte ptr BTRD[bx + 1],-1
je SNS6
mov ax,0
mov al,BTRD[bx + 1]
mov bx,ax
mov al,BTRD[bx + 2]
cmp al,BTRD[bx]
ja SNS5
;孩子为当前节点
mov ax,0
mov di,0
mov al,BTRD[bx + 2]
add di,ax
mov al,BTRD[bx + di + 6]
inc byte ptr BTRD[bx + 2]
mov bx,ax
jmp SNS
;当前节点没有未访问的孩子
;当前节点是根
SNS5:
cmp byte ptr BTRD[bx + 1],-1
je SNS6
jmp SNS4
SNS6:
;未找到
mov byte ptr BTRV[1],2
SNReturn:
pop si
pop di
pop dx
pop cx
pop bx
pop ax
ret
;-----------------------------------SearchNode end
;-----------------------------------InsertNode start
;在B树中插入关键字
;BTRV[0]存储要插入的关键字
;BTRV[1]存储返回值,1关键字已存在,2超过16个结点,3插入成功
InsertNode:
push ax
push bx
push di
push si
push cx
mov bx,0
mov di,0
mov bl,BOOT[0]
;是否存在树
cmp byte ptr BOOT[0],-1
jne INS
;不存在树
mov bx,0
mov byte ptr BTRD[bx],1
mov byte ptr BTRD[bx + 1],-1
mov byte ptr BTRD[bx + 2],0
mov al,BTRV[0]
mov byte ptr BTRD[bx + 3],al
mov byte ptr BTRD[bx + 6],-1
mov byte ptr BTRD[bx + 10],1
mov byte ptr BOOT[0],0
mov byte ptr BTRV[1],3
inc byte ptr NODENUM[0]
jmp INReturn
;存在树
;查找在当前节点中是否已存在关键字
INS:
mov cx,0
mov cl,BTRD[bx]
mov al,BTRV[0]
mov di,0
INS1:
cmp BTRD[bx + di + 3],al
je INS2
inc di
loop INS1
jmp INS3
;关键字已存在
;提示关键字已存在不可插入
INS2:
mov byte ptr BTRV[1],1
jmp INReturn
;当前节点是底层节点
INS3:
cmp byte ptr BTRD[bx + 6],-1
je INS6
;在当前节点找到合适位置向下搜索,选中的孩子为当前节点
mov cx,0
mov cl,BTRD[bx]
mov al,BTRV[0]
mov di,0
INS4:
cmp BTRD[bx + di + 3],al
ja INS5
inc di
loop INS4
;找到合适位置向下搜索
INS5:
mov ax,0
mov al,BTRD[bx + di + 6]
mov bx,ax
jmp INS
;是底层节点
;找到合适位置插入关键字
INS6:
cmp byte ptr BTRD[bx],2
jb INS18
cmp byte ptr NODENUM[0],16
jb INS18
mov byte ptr BTRV[1],2
jmp INReturn
INS18:
mov byte ptr BTRV[1],3
mov cx,0
mov cl,BTRD[bx]
mov al,BTRV[0]
mov di,0
INS7:
cmp BTRD[bx + di + 3],al
ja INS8
inc di
loop INS7
INS8:
;插入节点
call Insert
;关键字个数 > m - 1
INS10:
cmp byte ptr BTRD[bx],3
;插入成功
jb INR
jmp INR1
INR:
mov byte ptr BTRV[1],3
jmp INReturn
INR1:
;当前节点是根?
cmp byte ptr BTRD[bx + 1],-1
jne INS12
;当前节点是根
;中间关键字生成新根,原节点分裂成两个新节点
;对新根的处理
call Malloc
mov ax,0
mov al,BTRV[1]
mov BOOT[0],al
mov di,ax
mov al,BTRD[bx + 4]
mov BTRD[di + 3],al
mov byte ptr BTRD[di],1
mov byte ptr BTRD[di + 1],-1
mov byte ptr BTRD[di + 2],0
mov BTRD[di + 6],bl
mov byte ptr BTRV[2],0
mov byte ptr BTRV[3],0
jmp INS11
;当前节点不是根
;插入父节点中
INS12:
mov ax,0
mov al,BTRD[bx + 1]
mov di,ax
push di
mov al,0
INS15:
cmp BTRD[di + 6],bl
je INS16
inc al
inc di
jmp INS15
INS16:
mov di,ax
mov BTRV[3],al
mov al,BTRD[bx + 4]
mov BTRV[0],al
pop ax
push ax
push bx
mov bx,ax
call Insert
pop bx
pop di
mov byte ptr BTRV[2],1
;/////////////////////
INS11:
mov byte ptr BTRD[bx],1
mov ax,di
mov BTRD[bx + 1],al
;分裂出的新节点的处理
call Malloc
push di
mov ax,0
mov al,BTRV[1]
mov di,ax
mov al,BTRD[bx + 5]
mov BTRD[di + 3],al
cmp byte ptr BTRD[bx + 6],-1
jne INS13
mov byte ptr BTRD[di + 6],-1
jmp INS14
INS13:
mov al,BTRD[bx + 8]
mov BTRD[di + 6],al
mov al,BTRD[bx + 9]
mov BTRD[di + 7],al
push bx
mov bx,0
mov ax,di
mov bl,BTRD[di + 6]
mov BTRD[bx + 1],al
mov bl,BTRD[di + 7]
mov BTRD[bx + 1],al
pop bx
INS14:
mov byte ptr BTRD[di],1
mov byte ptr BTRD[di + 2],0
pop ax
mov si,ax
mov bx,ax
mov BTRD[di + 1],al
mov ax,0
mov al,BTRV[3]
inc ax
add si,ax
mov ax,di
mov BTRD[si + 6],al
cmp byte ptr BTRV[2],0
je INS19
jmp INS10
INS19:
mov byte ptr BTRV[1],3
INReturn:
pop cx
pop si
pop di
pop bx
pop ax
ret
;-----------------------------------InsertNode end
;-----------------------------------Malloc start
;在BTRD中寻找空间
;存储在BTRV[1]中
Malloc:
push bx
mov bx,0
MS:
cmp byte ptr BTRD[bx + 10],1
je MS1
jmp MReturn
MS1:
add bx,16
jmp MS
MReturn:
inc byte ptr NODENUM[0]
mov byte ptr BTRD[bx],0
mov byte ptr BTRD[bx + 2],0
mov byte ptr BTRD[bx + 10],1
mov BTRV[1],bl
pop bx
ret
;-----------------------------------Malloc end
;-----------------------------------Free start
;在BTRD中释放一个节点的空间
Free:
mov byte ptr BTRD[bx + 10],0
dec byte ptr NODENUM[0]
FReturn:
ret
;-----------------------------------Free end
;-----------------------------------Insert start
;在节点内部插入
;bx指向当前节点,di关键字的位置
;BTRV[0]存储插入的关键字
Insert:
push ax
push cx
push si
mov ax,di
cmp BTRD[bx],al
jne IS
mov al,BTRV[0]
mov BTRD[bx + di + 3],al
jmp IS1
;在内部插入
IS:
mov cx,0
mov cl,BTRD[bx]
sub cx,di
mov ax,0
mov al,BTRD[bx]
mov si,ax
push di
mov di,si
dec di
IS2:
mov al,BTRD[bx + di + 3]
mov BTRD[bx + si + 3],al
mov al,BTRD[bx + di + 7]
mov BTRD[bx + si + 7],al
dec di
dec si
loop IS2
pop di
mov al,BTRV[0]
mov BTRD[bx + di + 3],al
IS1:
inc byte ptr BTRD[bx]
IReturn:
pop si
pop cx
pop ax
ret
;-----------------------------------Insert end
;-----------------------------------DelBNode start
;在B树中删除节点
;BTRV[0]存储要删除的关键字
;BTRV[1]返回值1不存在树,2在整个树中未找到要删除的键,3删除成功
DelBNode:
push ax
push bx
push cx
push di
push si
mov bx,0
mov bl,BOOT[0]
mov byte ptr BTRV[1],0
cmp byte ptr BOOT[0],-1
jne DBNS
mov byte ptr BTRV[1],1
jmp DBNReturn
;在B树中查找关键字
;在当前节点查找要删除的关键字
DBNS:
mov cx,0
mov cl,BTRD[bx]
mov al,BTRV[0]
mov di,0
DBNS1:
cmp BTRD[bx + di + 3],al
je DBNS2
ja DBNS3
inc di
loop DBNS1
;在当前节点找到合适位置向下搜索,选中的孩子为当前节点
DBNS3:
cmp byte ptr BTRD[bx + 6],-1
je DBNS4
mov ax,0
mov al,BTRD[bx + di + 6]
mov bx,ax
jmp DBNS
;在整个树中未找到要删除的键
DBNS4:
mov byte ptr BTRV[1],2
jmp DBNReturn
;找到关键字删除
;当前节点是底层节点?
DBNS2:
cmp byte ptr BTRD[bx + 6],-1
je DBNS5
;节点不是底层节点,替换操作
;找到这个节点的中序前驱节点
push bx
push di
mov ax,0
mov al,BTRD[bx + di + 6]
mov bx,ax
DBNS15:
cmp byte ptr BTRD[bx + 6],-1
je DBNS14
mov ax,0
mov al,BTRD[bx]
mov di,ax
mov ax,0
mov al,BTRD[bx + di + 6]
mov bx,ax
jmp DBNS15
;前驱节点的最大关键字上移到父关键字
DBNS14:
mov si,bx
pop di
pop bx
push si
mov ax,0
mov al,BTRD[si]
dec al
add si,ax
mov al,BTRD[si + 3]
mov BTRD[bx + di + 3],al
pop bx
dec byte ptr BTRD[bx]
jmp DBNS12
;删除关键字,移位操作
DBNS5:
dec byte ptr BTRD[bx]
;移位操作
mov cx,0
mov cl,BTRD[bx]
sub cx,di
cmp cx,0
je DBNSS1
DBNSS:
mov al,BTRD[bx + di + 4]
mov BTRD[bx + di + 3],al
inc di
loop DBNSS
DBNSS1:
cmp byte ptr BTRD[bx + 1],-1
jne DBNS12
;当前节点是根
cmp byte ptr BTRD[bx],0
ja DBNS13
mov byte ptr BOOT[0],-1
DBNS13:
mov byte ptr BTRV[1],3
jmp DBNReturn
;关键字是否 > = m / 2 - 1
DBNS12:
cmp byte ptr BTRD[bx],1
jb DBNS6
;删除结束
mov byte ptr BTRV[1],3
jmp DBNReturn
;当前节点关键字个数 < m / 2 - 1
;回溯到父节点
DBNS6:
push bx
mov ax,0
mov al,BTRD[bx + 1]
mov bx,ax
pop ax
mov cx,0
mov cl,BTRD[bx]
inc cx
mov di,0
DBNS7:
cmp BTRD[bx + di + 6],al
je DBNS8
inc di
loop DBNS7
;这个节点是否存在右兄弟
DBNS8:
mov ax,0
mov al,BTRD[bx]
cmp di,ax
je DBNS18
;这个节点的右兄弟是否 > m / 2 - 1
mov ax,0
mov al,BTRD[bx + di + 7]
mov si,ax
cmp byte ptr BTRD[si],1
jna DBNS9
call MoveRightNode
jmp DBNReturn
DBNS18:
dec di
mov TEMP[0],di
jmp DBNS19
;是否存在左兄弟
DBNS9:
cmp di,0
je DBNS10
mov TEMP[0],di
dec di
;左兄弟节点关键字是否 > m / 2 - 1
DBNS19:
mov ax,0
mov al,BTRD[bx + di + 6]
mov si,ax
cmp byte ptr BTRD[si],1
jna DBNS20
call MoveLeftNode
jmp DBNReturn
DBNS20:
mov di,TEMP[0]
;合并
DBNS10:
call JoinNode
cmp byte ptr BTRD[bx + 1],-1
jne DBNS21
cmp byte ptr BTRD[bx],1
jb DBNS16
jmp DBNReturn
DBNS21:
jmp DBNS12
DBNS16:
mov ax,0
mov al,BTRD[bx + 6]
call Free
mov bx,ax
mov BOOT[0],al
mov BTRD[bx + 1],-1
DBNReturn:
pop si
pop di
pop cx
pop bx
pop ax
ret
;-----------------------------------DelBNode end
;-----------------------------------JoinNode start
;左右孩子节点都 < = m / 2 - 1
;合并父关键字,与其对应的两个子树到左孩子
;把这个键右边的键和对应的右子树左移
JoinNode:
push ax
push bx
push cx
push di
push si
dec byte ptr BTRD[bx]
;把这个键下移到它的左子树
mov ax,0
mov al,BTRD[bx + di + 6]
mov si,ax
push si
add al,BTRD[si]
mov si,ax
mov al,BTRD[bx + di + 3]
mov BTRD[si + 3],al
pop si
inc byte ptr BTRD[si]
;把右子树中的所有键值和子树转移到左子树
push di
mov ax,0
mov al,BTRD[bx + di + 7]
mov di,ax
push di
push si
mov ax,si
add al,BTRD[si]
mov si,ax
mov cx,0
mov cl,BTRD[di]
cmp cx,0
je JNSS4
JNSS:
mov al,BTRD[di + 3]
mov BTRD[si + 3],al
mov al,BTRD[di + 6]
mov BTRD[si + 6],al
inc si
inc di
loop JNSS
JNSS4:
mov al,BTRD[di + 6]
mov BTRD[si + 6],al
pop si
pop di
mov al,BTRD[di]
add BTRD[si],al
;销毁右子树
push bx
mov bx,di
push di
cmp byte ptr BTRD[bx + 6],-1
je JNSS3
;更新右子树转到左子树的节点的父指针
mov cx,0
mov cl,BTRD[di]
mov bx,si
inc cx
JNSS2:
mov ax,0
mov al,BTRD[di + 6]
mov si,ax
mov BTRD[si + 1],bl
inc di
loop JNSS2
JNSS3:
pop bx
call Free
pop bx
pop di
;这个节点右边的关键字和对应的右子树向左移动
mov cx,0
mov cl,BTRD[bx]
sub cx,di
cmp cx,0
je JNReturn
JNSS1:
mov al,BTRD[bx + di + 4]
mov BTRD[bx + di + 3],al
mov al,BTRD[bx + di + 8]
mov BTRD[bx + di + 7],al
inc di
loop JNSS1
JNReturn:
pop si
pop di
pop cx
pop bx
pop ax
ret
;-----------------------------------JoinNode end
;-----------------------------------MoveRightNode start
;从一个键的右子树向左子树转移一个键,使两个子树平衡
;右孩子节点 > m / 2 - 1
;右孩子中最小的关键字上移到父关键字
MoveRightNode:
push ax
push cx
push si
;把这个键下移到它的左子树
mov ax,0
mov al,BTRD[bx + di + 6]
mov si,ax
push si
add al,BTRD[si]
mov si,ax
mov al,BTRD[bx + di + 3]
mov BTRD[si + 3],al
pop si
inc byte ptr BTRD[si]
;把右子树的最左子树转移成左子树的最右子树
push di
mov ax,0
mov al,BTRD[bx + di + 7]
mov di,ax
cmp byte ptr BTRD[di + 6],-1
je MRNS
;左右子树不是底层节点
push si
mov ax,si
add al,BTRD[si]
mov si,ax
mov ax,0
mov al,BTRD[di + 6]
mov BTRD[si + 6],al
pop si
push di
mov di,ax
mov cx,si
mov BTRD[di + 1],cl
pop di
jmp MRNS1
;左右子树是底层节点
MRNS:
mov byte ptr BTRD[di + 7],-1
;把右子树的最左键提升到这个键的位置上
MRNS1:
mov si,di
pop di
mov al,BTRD[si + 3]
mov BTRD[bx + di + 3],al
dec byte ptr BTRD[si]
;把右子树中的所有键值和对应的子树左移 1 个位置
mov cx,0
mov cl,BTRD[si]
cmp cx,1
jb MRNReturn
MRNS2:
mov al,BTRD[si + 4]
mov BTRD[si + 3],al
mov al,BTRD[si + 7]
mov BTRD[si + 6],al
inc si
loop MRNS2
mov al,BTRD[si + 7]
mov BTRD[si + 6],al
MRNReturn:
pop si
pop cx
pop ax
ret
;-----------------------------------MoveRightNode end
;-----------------------------------MoveLeftNode start
;从一个键的左子树向右子树转移一个键,使两个子树平衡
;左孩子节点 > m / 2 - 1
;左孩子中最大的关键字上移到父关键字
MoveLeftNode:
push ax
push cx
push si
;右子树中所有的键值和对应的子树向右移 1 个位置
mov ax,0
mov al,BTRD[bx + di + 7]
mov si,ax
push si
mov cx,0
mov cl,BTRD[si]
add ax,cx
mov si,ax
cmp cx,1
jb MLNS3
MLNS:
mov al,BTRD[si + 2]
mov BTRD[si + 3],al
mov al,BTRD[si + 6]
mov BTRD[si + 7],al
dec si
loop MLNS
MLNS3:
mov al,BTRD[si + 6]
mov BTRD[si + 7],al
;把这个键下移到它的右子树
pop si
mov al,BTRD[bx + di + 3]
mov BTRD[si + 3],al
inc byte ptr BTRD[si]
;把左子树的最右子树转移成右子树的最左子树
push di
mov ax,0
mov al,BTRD[bx + di + 6]
mov di,ax
cmp byte ptr BTRD[di + 6],-1
je MLNS1
;左右孩子不是底层节点
push di
mov ax,di
add al,BTRD[di]
mov di,ax
mov ax,0
mov al,BTRD[di + 6]
mov BTRD[si + 6],al
mov di,ax
mov cx,si
mov BTRD[di + 1],cl
pop di
jmp MLNS2
;左右孩子是底层节点
;右子树
MLNS1:
mov byte ptr BTRD[si + 6],-1
;左孩子中最大的关键字上移到这个键的位置上
MLNS2:
mov si,di
pop di
push si
mov ax,si
add al,BTRD[si]
mov si,ax
dec si
mov al,BTRD[si + 3]
mov BTRD[bx + di + 3],al
pop si
dec byte ptr BTRD[si]
MLNReturn:
pop si
pop cx
pop ax
ret
;-----------------------------------MoveLeftNode end
code ends
end start
[07/11/22] |