Zrušení položky z RB-stromu


; -----------------------------------------------------------------------------
;                  Delete node from red-black balanced tree
; -----------------------------------------------------------------------------
; INPUT:	EBX = pointer to deleted node (RBNODE)
;		EDX = pointer to root (RBROOT)
; NOTES:	RBNODE memory block is not destroyed.
; -----------------------------------------------------------------------------
; Local variables:
%define		RBPa	EAX			; parent
%define		RBPaL	AL			; parent LOW
%define		RBNo	EBX			; current node
%define		RBCo	ECX			; color
%define		RBCoL	CL			; color LOW
%define		RBRo	EDX			; root
%define		RBOl	ESI			; old node
%define		RBCh	EDI			; child

; ------------- Push registers

RBTreeDelete:	push	RBPa			; push RBPa
		push	RBNo			; push RBNo
		push	RBCo			; push RBCo
		push	RBOl			; push RBOl
		push	RBCh			; push RBCh

; ------------- Decrease number of entries

		dec	dword [RBRo+RBR_Count]	; decrease number of entries

; ------------- Detach entry from the list

		call	ListDelEBX		; delete node

; ------------- Get child node from right node if left node is not valid

		mov	RBCh,[RBNo+RBN_Right]	; RBCh <- get right node
		mov	RBOl,[RBNo+RBN_Left]	; RBOl <- get left node
		or	RBOl,RBOl		; ir left node valid?
		jz	RBTreeDelete6		; left node is not valid

; ------------- Get child node from left node if right node is not valid

		xchg	RBOl,RBCh		; child <- left, old <- right
		or	RBOl,RBOl		; is right node valid?
		jz	RBTreeDelete6		; right node is not valid

; ------------- Find leftmost node of right node

		mov	RBCh,RBOl		; child <- save right node
		mov	RBOl,RBNo		; old <- save current node
RBTreeDelete1:	mov	RBNo,RBCh		; node <- right/left
		mov	RBCh,[RBNo+RBN_Left]	; child <- get left node
		or	RBCh,RBCh		; is left node valid?
		jnz	RBTreeDelete1		; next left node

; ------------- Get right child, parent and color of the node

		mov	RBCh,[RBNo+RBN_Right]	; child <- get right node
		mov	RBPa,[RBNo+RBN_Parent]	; parent <- get parent
		mov	RBCoL,[RBNo+RB_Color]	; color <- get color

; ------------- Link parent to right child

		or	RBCh,RBCh		; is child valid?	
		jz	RBTreeDelete2		; child is not valid
		mov	[RBCh+RBN_Parent],RBPa	; child <- set new parent

; ------------- If parent is old (deleted) node link it as its right node

RBTreeDelete2:	cmp	RBOl,RBPa		; is parent equal to old node?
		jne	RBTreeDelete3		; parent is not old node
		mov	[RBPa+RBN_Right],RBCh	; set child as right of parent
		mov	RBPa,RBNo		; parent <- node
		jmp	short RBTreeDelete4
RBTreeDelete3:	mov	[RBPa+RBN_Left],RBCh	; set child as left of parent

; ------------- Copy color, right and left node from old node to current one

RBTreeDelete4:	push	RBPa			; push RBPa (old parent)
		mov	RBPaL,[RBOl+RB_Color]	; color
		mov	[RBNo+RB_Color],RBPaL
		mov	RBPa,[RBOl+RBN_Left]	; left node
		mov	[RBNo+RBN_Left],RBPa
		mov	RBPa,[RBOl+RBN_Right]	; right node
		mov	[RBNo+RBN_Right],RBPa
		mov	RBPa,[RBOl+RBN_Parent]	; parent
		mov	[RBNo+RBN_Parent],RBPa

; ------------- Link current node to parent

		or	RBPa,RBPa		; is parent valid?
		jz	RBTreeDelete56		; parent is not valid
		cmp	[RBPa+RBN_Left],RBOl	; old node=left node of parent?
		jne	RBTreeDelete52		; no
		mov	[RBPa+RBN_Left],RBNo	; node -> left node of parent
		jmp	short RBTreeDelete58
RBTreeDelete52:	mov	[RBPa+RBN_Right],RBNo	; node -> right node of parent
		jmp	short RBTreeDelete58
RBTreeDelete56:	mov	[RBRo+RBR_Node],RBNo	; node -> root node

; ------------- Link current node as parent of old left node

RBTreeDelete58:	mov	RBPa,[RBOl+RBN_Left]	; RBPa <- get old left node
		mov	[RBPa+RBN_Parent],RBNo	; node -> parent of left node

; ------------- Link current node as parent of old right node

		mov	RBPa,[RBOl+RBN_Right]	; RBPa <- get old right node
		or	RBPa,RBPa		; is old right node valid?
		jz	RBTreeDelete59		; old right node is not valid
		mov	[RBPa+RBN_Parent],RBNo	; node -> parent of right node
RBTreeDelete59:	pop	RBPa			; pop RBPa (old parent)
		jmp	short RBTreeDelete7	; delete color

; ------------- Get parent and color of current node

RBTreeDelete6:	mov	RBPa,[RBNo+RBN_Parent]	; RBPa <- get current parent
		mov	RBCoL,[RBNo+RB_Color]	; RBCoL <- get current color

; ------------- Link parent as new parent of the child

		or	RBCh,RBCh		; is child valid?
		jz	RBTreeDelete62		; child is not valid
		mov	[RBCh+RBN_Parent],RBPa	; parent -> parent of the child

; ------------- Link child to the parent

RBTreeDelete62:	or	RBPa,RBPa		; is parent valid?
		jz	RBTreeDelete66		; parent is not valid
		cmp	RBNo,[RBPa+RBN_Left]	; is current node left child?
		jne	RBTreeDelete64		; is it not left child
		mov	[RBPa+RBN_Left],RBCh	; link child as left child
		jmp	short RBTreeDelete7
RBTreeDelete64:	mov	[RBPa+RBN_Right],RBCh	; link child as right child
		jmp	short RBTreeDelete7
RBTreeDelete66:	mov	[RBRo+RBR_Node],RBCh	; child -> root node

; ------------- Delete color

RBTreeDelete7:	cmp	RBCoL,RB_BLACK		; is it black color?
		jne	RBTreeDelete8		; it is not black color
		mov	ebx,RBCh		; EBX <- child node
		call	RBTreeDelCol		; delete color

; ------------- Pop registers

RBTreeDelete8:	pop	RBCh			; pop RBCh
		pop	RBOl			; pop RBOl
		pop	RBCo			; pop RBCo
		pop	RBNo			; pop RBNo
		pop	RBPa			; pop RBPa
		ret

Funkce RBTreeDelete zruší položku z RB-stromu. Vstupními parametry funkce jsou v registru EBX ukazatel na rušenou položku a v registru EDX ukazatel na kořen stromu. Funkce používá namísto jmen registrů jejich symbolická označení: RBPa (EAX) označuje rodiče položky, RBPaL (AL) je jeho nejnižší bajt, RBNo (EBX) je ukazatel na aktuální položku (na začátku funkce je to rušená položka), RBCo (ECX) je registr s barvou položky, RBCoL (CL) je jeho nejnižší bajt, RBRo (EDX) je ukazatel na kořen stromu, RBOl (ESI) je ukazatel na starou položku a RBCh (EDI) je ukazatel na potomka aktuální položky.

Na začátku funkce jsou uchovány použité registry, snížen čítač položek ve stromu a rušená položka je odpojena od seznamu položek ve stromu.

Nejjednodušší případ nastane, má-li rušená položka pouze jednoho potomka nebo nemá-li žádného potomka. V tom případě postačí připojit potomka k rodiči namísto rušené položky, protože potomek patří do stejné větve jako patřila rušená položka.

Do registru RBCh je načten pravý potomek rušené položky a do registru RBOl je připraven levý potomek. Není-li ukazatel na levého potomka platný (tj. je NULL), použije se ukazatel na pravého potomka jako potomek aktuální položky, kterým má být nahrazena rušená položka. Je-li levý potomek platný a pravý potomek neplatný, použije se levý potomek jako potomek rušené položky.

V obou uvedených případech pokračuje funkce na návěští RBTreeDelete6. Do registru RBPa je načten ukazatel na rodiče rušené položky a do registru RBCoL barva rušené položky. Je-li potomek rušené položky platný, nastaví se rodič jako jeho nový rodič.

Potomek rušené položky se připojí k rodiči. Je-li rodičem kořen stromu (ukazatel na rodiče je NULL), je ukazatel na potomka nastaven jako nová výchozí položka kořene stromu. Jinak se ukazatel na potomka nastaví jako potomek rodiče a to tak, že porovnáním rušené položky s levým potomkem rodiče se provede test, zda byla rušená položka levým nebo pravým potomkem a podle toho se uloží ukazatel na potomka do levého nebo pravého ukazatele. Dále obsluha pokračuje společnou částí - oprava barvy po zrušení položky (funkce RBTreeDelCol), ale to jen v případě, že rušená položka měla černou barvu.

Nyní zpět k případu, kdy jsou oba potomci rušené položky platní (tj. zpět k návěští RBTreeDelete1). Strom musíme přestavět tak, abychom našli nejbližší položku k původní rušené položce, kterou rušenou položku nahradíme. Zvolíme položku, která se nachází nejvíce vlevo od pravého potomka.

Do registru RBCh si uschováme ukazatel na pravého potomka rušené položky a do registru RBOl ukazatel na aktuální (rušenou) položku. Nyní budeme v cyklu procházet levé větve, až narazíme na neplatný ukazatel. V registru RBNo nám zůstane položka pravého potomka, která se nachází nejvíce vlevo, což je nejbližší položka (z pravé strany) k původní rušené položce.

Z nové aktuální položky si do registru RBCh připravíme ukazatel na pravého potomka (tím musíme nahradit odpojenou novou aktuální položku - víme přitom, že levý potomek nové aktuální položky je neplatný), do registru RBPa ukazatel na rodiče nové aktuální položky a do registru RBCoL barvu nové aktuální položky.

Je-li pravý potomek nové aktuální položky platný, nastaví se rodič nové aktuální položky jako rodič pravého potomka. Je-li rodičem nové aktuální položky původní rušená položka (RBTreeDelete2), znamená to, že nová aktuální položka je pravým potomkem rušené položky a proto bude ukazatel na pravého potomka nové aktuální položky uložen jako pravá položka rušené položky a nová aktuální položka bude novým rodičem, jinak se ukazatel na pravého potomka nové aktuální položky uloží jako levá položka rodiče nové aktuální položky, v obou případech tak bude nová položka nahrazena svým potomkem.

Nyní bude původní rušená položka nahrazena novou aktuální položkou. Z původní rušené položky se do nové aktuální položky přenese barva, levý a pravý potomek a rodič. Ukazatel na novou aktuální položku se uloží do rodiče - opět se rozliší případy kořen, levý a pravý potomek.

Nová aktuální položka se nastaví jako nový rodič levého potomka původní rušené položky (z testů na začátku funkce víme, že levý potomek je platný) a také jako rodič pravého potomka původní rušené položky (z testů sice víme, že pravý potomek byl platný, ale mohl být nahrazen pravým potomkem nové aktuální položky, který již může být neplatný). Dále se již pokračuje společnou částí - oprava barvy po zrušení položky (funkce RBTreeDelCol), ale to jen v případě, že rušená položka měla černou barvu.


; -----------------------------------------------------------------------------
;              Delete color of node from red-black balanced tree
; -----------------------------------------------------------------------------
; INPUT:	EAX = pointer to parent of node (RBNODE, NULL=root)
;		EBX = pointer to new current node
;		EDX = pointer to root (RBROOT)
; NOTES:	Entry point is RBTreeDelCol.
; -----------------------------------------------------------------------------
; Local variables:
%define		RBPa	EAX			; parent
%define		RBNo	EBX			; deleted node
%define		RBNe	ECX			; nephew (hardcoded)
%define		RBNeL	CL			; nephew LOW (temporary reg.)
%define		RBRo	EDX			; root
%define		RBBr	ESI			; brother

; ============= RBTreeDelCol function

; ------------- Push registers

RBTreeDelCol:	push	RBPa			; push RBPa
		push	RBNo			; push RBNo
		push	RBNe			; push RBNe
		push	RBBr			; push RBBr

; ------------- Node must be black or invalid

RBTreeDelCol2:	or	RBNo,RBNo		; is node valid?
		jz	short RBTreeDelCol3	; node is not valid
		CMPBLK	RBNo			; is node black?
		jne	RBTreeDelCol6		; node is not black

; ------------- Node must not be a root node

RBTreeDelCol3:	cmp	RBNo,[RBRo+RBR_Node]	; is it root node?
		je	RBTreeDelCol6		; it is root node

; ------------- Check if current node is left node of parent

		cmp	RBNo,[RBPa+RBN_Left]	; is current node left node?
		jne	near RBTreeDelCol5	; it is not left node

; ------------- Node is left node

		RBTreeDelC Left, Right		; delete color for left
		jmp	RBTreeDelCol6		; quit

; ------------- Node is right node

RBTreeDelCol5:	RBTreeDelC Right, Left		; delete color for right

; ------------- Set node to black

RBTreeDelCol6:	or	RBNo,RBNo		; is node valid?
		jz	short RBTreeDelCol8	; node is invalid
		SETBLK	RBNo			; set node to black

; ------------- Pop registers

RBTreeDelCol8:	pop	RBBr			; pop RBBr
		pop	RBNe			; pop RBNe
		pop	RBNo			; pop RBNo
		pop	RBPa			; pop RBPa
		ret

Funkce RBTreeDelCol je pomocnou funkcí pro funkci RBTreeDelete a zajišťuje vyvážení stromu po zrušení položky ze stromu. Vstupními parametry funkce jsou v registru EAX ukazatel na rodiče nové aktuální položky, v registru EBX ukazatel na novou aktuální položku (která nahradila původní rušenou položku) a v registru EDX ukazatel na kořen stromu. Funkce používá namísto registrů jejich symbolická jména: RBPa (EAX) je rodič nové aktuální položky, RBNo (EBX) je nová aktuální položka, RBNe (ECX) je synovec aktuální položky, nebo-li potomek bratra, RBNeL (CL) je nižší bajt synovce (používá se jako přechodný registr), RBRo (EDX) je ukazatel na kořen stromu a RBBr (ESI) je bratr aktuální položky, nebo-li sousední položka aktuální položky patřící ke stejnému rodiči.

Na začátku funkce je provedeno několik testů. Je-li aktuální položka platná a nemá-li černou barvu, je funkce ukončena nastavením černé barvy aktuální položky. Podobně je funkce ukončena v případě, že aktuální položka je kořenovou položkou stromu.

Dále je porovnáním ukazatele na aktuální položku s ukazatelem na levého potomka rodiče rozlišeno, zda je aktuální položka levým nebo pravým potomkem a podle toho je voláno makro RBTreeDelC, které zajistí opravu stromu pro daný směr. Po obsluze makra je nastavena barva aktuální položky na černou barvu.


; ============= Macros

; ------------- Macro - check if left (right) nephew is black
; Parameters: %1 = Left (Right), %2 = jump label if nephew is not black

%macro		TESTNE	2

		mov	RBNe,[RBBr+RBN_%1]	; get nephew
		jecxz	%%black			; nephew is not valid
		CMPBLK	RBNe			; is nephew black?
		jne	%2			; nephew is not black
%%black:

%endmacro

; ------------- Macro - delete color in one direction
; Parameters (direction word): %1 = Left (Right), %2 = Right (Left)

%macro		RBTreeDelC 2

; ------------- Get brother node from right (left) and check if it is red
; Node is black or invalid and therefore its brother is always valid

		mov	RBBr,[RBPa+RBN_%2]	; get brother node
		CMPRED	RBBr			; is brother node red?
		jne	short %%L2		; brother node is not red

; ------------- Set brother node black, set parent red a rotate it left (right)

		SETBLK	RBBr			; set brother node black
		SETRED	RBPa			; set parent node red
		push	RBNo			; push RBNo
		mov	RBNo,RBPa		; parent node will be used
		call	RBTree%1		; rotate parent left (right)
		pop	RBNo			; pop RBNo
		mov	RBBr,[RBPa+RBN_%2]	; get new brother node

; ------------- Check if left (right) nephew is black

%%L2:		TESTNE	%1, %%L4		; check left (right) nephew

; ------------- Check if right (left) nephew is black

		TESTNE	%2, %%L4		; check right (left) nephew

; ------------- Set brother to red

		SETRED	RBBr			; set brother to red
		mov	RBNo,RBPa		; node <- parent
		mov	RBPa,[RBNo+RBN_Parent]	; get new parent
		jmp	RBTreeDelCol2		; next node
		
; ------------- Check if right (left) nephew is black

%%L4:		TESTNE	%2, %%L6		; check right (left) nephew

; ------------- Set left (right) nephew to black

		mov	RBNe,[RBBr+RBN_%1]	; get left (right) nephew
		jecxz	%%L5			; nephew is not valid
		SETBLK	RBNe			; set nephew black

; ------------- Set brother red and rotate it right (left)

%%L5:		SETRED	RBBr			; set brother red
		push	RBNo			; push RBNo
		mov	RBNo,RBBr		; node <- brother
		call	RBTree%2		; rotate brother right (left)
		pop	RBNo			; pop RBNo
		mov	RBBr,[RBPa+RBN_%2]	; get new brother node

; ------------- Copy parent's color to brother

%%L6:		mov	RBNeL,[RBPa+RB_Color]	; get parent's color
		mov	[RBBr+RB_Color],RBNeL	; set brother's color
		SETBLK	RBPa			; set parent black

; ------------- Set right (left) nephew to black

		mov	RBNe,[RBBr+RBN_%2]	; get right (left) nephew
		jecxz	%%L8			; nephew is not valid
		SETBLK	RBNe			; set nephew black

; ------------- Rotate parent left (right)

%%L8:		mov	RBNo,RBPa		; parent will be used
		call	RBTree%1		; rotate parent left (right)
		mov	RBNo,[RBRo+RBR_Node]	; get root node
%endmacro

Makro RBTreeDelC zajistí vyvážení větve stromu pro daný aktuální uzel. Makro má dva parametry - texty názvů přilehlé a protilehlé strany. Pro zrušení barvy položky, která je levým potomkem rodiče, jsou parametry Left a Right, pro zrušení barvy pravé položky jsou parametry Right a Left. Parametry jsou v makru dosazeny do jmen proměnných (např. RBN_%2 se nahradí textem RBN_Left).

Makro RBTreeDelC používá pomocné makro TESTNE, které testuje synovce (nebo-li potomka bratra) pro směr daný prvním parametrem makra - je-li synovec platný a má-li červenou barvu, provede se skok na návěští dané druhým parametrem makra.

Na začátku makra RBTreeDelC je do registru RBBr načten bratr aktuální položky, nebo-li položka rodiče z opačného směru. Víme, že aktuální položka má černou barvu nebo je neplatná a proto bude bratr platný. Má-li bratr červenou barvu, změní se barva bratra na černou barvu, barva rodiče se změní na červenou barvu a rodič se rotací ve shodném směru (tj. pro levou aktuální položku směr doleva) vyváží tak, že bratr bude novým rodičem. Ukazatel na bratra se obnoví načtením nové protější položky z rodiče.

Provedou se testy barev synovců (potomků bratra). Jsou-li oba synovci černí nebo neplatní, změní se barva bratra na červenou, rodič se stane novou aktuální položkou, načte se jeho rodič a pokračuje se dále obsluhou nové položky (návěští RBTreeDelCol2).

Opětovným testem protilehlého synovce se rozliší, zda byl protilehlý synovec černý nebo neplatný. Pokud ano, znamená to, že přilehlý synovec je červený. Načte se ukazatel na přilehlého synovce a nastaví se jeho barva na černou.

Barva bratra se opraví na červenou (protože oba synovci jsou černí nebo neplatní) a bratr se rotuje v opačném směru, takže přilehlý synovec (původně červený) se stane novým bratrem. Ukazatel na nového bratra je načten z rodiče jako ukazatel na protější položku.

Barva rodiče se přenese do barvy bratra a rodič se nastaví na černou barvu. Protilehlý synovec se nastaví také na černou barvu (je-li platný). Nakonec se rodič rotuje v přilehlém směru, takže bratr se přesune na místo rodiče.