Struktura popisovačů RB-stromu


; ------------- Red-black common head

struc		RBCOMMON

		resb	LIST_size	; 0: list of entries
RB_ColorFlags:
RB_Color:	resb	1		; 8: color of node (see below)
RB_Flags:	resb	1		; 9: flags (see below)
RB_DataW:	resw	1		; 0Ah: possible data of tree node, WORD

endstruc				; size 12 bytes

; ------------- Red-black color of node

RB_RED		EQU	0		; red color of node (hardcoded)
RB_BLACK	EQU	1		; black color of node

; ------------- Red-black flags

RB_ROOT		EQU	B0		; this is the root (else this is node)

; ------------- Red-black balanced tree root

struc		RBROOT

		resb	RBCOMMON_size	; common head (list and flags)
RBR_Node:	resd	1		; 0Ch: pointer to first node (0=empty)
RBR_Count:	resd	1		; 10h: number of nodes in the tree

endstruc				; size 14h = 20 bytes

; ------------- Red-black balanced tree node

struc		RBNODE

		resb	RBCOMMON_size	; common head (list and flags)
RBN_Parent:	resd	1		; 0Ch: parent node (NULL=root)
RBN_Left:	resd	1		; 10h: left node (lower, 0=none)
RBN_Right:	resd	1		; 14h: right node (higher, 0=none)
					;      (hardcoded: right = left + 4)
RBN_Data:				; 18h: possible data of tree node

endstruc				; size 18h = 24 bytes

Kořen i uzel RB-stromu používají společnou část popisovače, RBCOMMON. Struktura RBCOMMON obsahuje na svém začátku popisovač seznamu položek LIST, který slouží k rychlému procházení seznamu po položkách. Za popisovačem seznamu je proměnná RB_Color, která obsahuje barvu uzlu. Možné hodnoty jsou RB_RED (= číslo 0) a RB_BLACK (= číslo 1). Následuje proměnná RB_Flags obsahující příznaky. Jediným možným příznakem je bit RB_ROOT, který indikuje, že položka je kořenem stromu (root) a neobsahuje tedy platná data. Není-li bit RB_ROOT nastaven, jedná se o běžný uzel stromu. Poslední proměnnou je RB_DataW. Jedná se o volitelnou proměnnou, která může být použita k uložení třídicího klíče uzlů.

Popisovač kořene stromu RBROOT obsahuje na svém začátku společný popisovač RBCOMMON s nastaveným příznakem RB_ROOT. Za ním následuje proměnná RBR_Node, což je ukazatel na výchozí (kořenový) uzel stromu. Je-li vynulován, neobsahuje strom žádný uzel. Za ukazatelem následuje proměnná RBR_Count obsahující celkový počet uzlů ve stromu. Kořen stromu je pouze popisovačem stromu, není uzlem stromu s platnými daty.

Popisovač uzlu stromu RBNODE obsahuje na svém začátku společný popisovač RBCOMMON s vynulovaným příznakem RB_ROOT. Za ním následuje proměnná RBN_Parent, což je ukazatel na uzel rodiče. Obsahuje-li nulu, je rodičem kořen stromu. Další dva ukazatele, RBN_Left a RBN_Right, ukazují na levý a pravý uzel stromu. Levý uzel má nižší hodnotu třídicího klíče, pravý uzel vyšší hodnotu. Obsahují-li ukazatele nulu, nenásleduje žádný další uzel. Návěští RBN_Data označuje začátek možných dat uzlu. Z důvodu efektivnosti algoritmů je požadováno, aby proměnná s ukazatelem na pravý uzel následovala bezprostředně za proměnnou s ukazatelem na levý uzel.