Slett-funksjonen brukes til å slette den angitte noden fra et binært søketre. Imidlertid må vi slette en node fra et binært søketre på en slik måte at egenskapen til binært søketre ikke bryter. Det er tre situasjoner for å slette en node fra binært søketre.
Noden som skal slettes er en bladnode
Det er det enkleste tilfellet, i dette tilfellet erstatt bladnoden med NULL og enkelt frigjør den tildelte plassen.
I det følgende bildet sletter vi noden 85, siden noden er en bladnode, derfor vil noden bli erstattet med NULL og tildelt plass vil bli frigjort.
Noden som skal slettes har bare ett barn.
Erstatt i dette tilfellet noden med dens underordnede node og slett den underordnede noden, som nå inneholder verdien som skal slettes. Bare erstatt den med NULL og frigjør den tildelte plassen.
I det følgende bildet skal noden 12 slettes. Den har bare ett barn. Noden vil bli erstattet med sin underordnede node og den erstattede noden 12 (som nå er bladnode) vil ganske enkelt bli slettet.
Noden som skal slettes har to barn.
Det er en litt komplisert sak sammenlignet med andre to saker. Imidlertid erstattes noden som skal slettes med sin i rekkefølge etterfølger eller forgjenger rekursivt inntil nodeverdien (som skal slettes) er plassert på bladet av treet. Etter prosedyren, erstatt noden med NULL og frigjør den tildelte plassen.
I det følgende bildet skal noden 50 slettes som er rotnoden til treet. Traverseringen av treet i rekkefølge gitt nedenfor.
6, 25, 30, 50, 52, 60, 70, 75.
erstatt 50 med sin etterfølger 52 i rekkefølge. Nå vil 50 bli flyttet til bladet på treet, som ganske enkelt slettes.
Algoritme
Slett (TRE, ITEM)
Skriv 'element ikke funnet i treet' ELLERS HVIS VAREDATA
Slett(TRE->VENSTRE, ITEM)
ANNET HVIS VARE > TRE -> DATA
Slett(TRE -> HØYRE, ITEM)
ANNET HVIS TRE -> VENSTRE OG TRE -> HØYRE
SET TEMP = findLargestNode(TREE -> VENSTRE)
SETTTRE -> DATA = TEMP -> DATA
Slett(TRE -> VENSTRE, TEMP -> DATA)
ELLERS
SET TEMP = TRE
HVIS TRE -> VENSTRE = NULL OG TRE -> HØYRE = NULL
SETTREE = NULL
ANDRE HVIS TRE -> VENSTRE != NULL
SET TRE = TRE -> VENSTRE
ELLERS
SET TRE = TRE -> HØYRE
[SLUT PÅ HVIS]
FRI TEMP
[SLUT PÅ HVIS]
Funksjon:
void deletion(Node*& root, int item) { Node* parent = NULL; Node* cur = root; search(cur, item, parent); if (cur == NULL) return; if (cur->left == NULL && cur->right == NULL) { if (cur != root) { if (parent->left == cur) parent->left = NULL; else parent->right = NULL; } else root = NULL; free(cur); } else if (cur->left && cur->right) { Node* succ = findMinimum(cur- >right); int val = succ->data; deletion(root, succ->data); cur->data = val; } else { Node* child = (cur->left)? Cur- >left: cur->right; if (cur != root) { if (cur == parent->left) parent->left = child; else parent->right = child; } else root = child; free(cur); } } Node* findMinimum(Node* cur) { while(cur->left != NULL) { cur = cur->left; } return cur; }