Fala galera!
No último post nós vimos algumas funções para calcular o tamanho e altura de nossa Binary Search Tree (BST)
.
Hoje será o último post sobre os exercícios com BST
e nós criaremos a função para remover nodos.
Revisão da BST
Vamos apenas recapitular como eram as funções size
e height
que trabalhamos no post anterior.
Primeiro a função size
para trabalhar com uma BST
que significa obter o número de elementos que existem em uma BST
.
BST
.
size :: (Ord a) => Tree a -> Int
size Empty = 0
size (Node _ left right) = 1 + (size left) + (size right)
> let tree = build [8,6,9,4,7,11,10,12,8,6,2,3,1]
> tree
Node 8 (Node 6 (Node 4 (Node 2 (Node 1 Empty Empty) (Node 3 Empty Empty)) (Node 6 Empty Empty)) (Node 7 Empty (Node 8 Empty Empty))) (Node 9 Empty (Node 11 (Node 10 Empty Empty) (Node 12 Empty Empty)))
> size tree
13
> let newTree = find tree 6
> newTree
Node 6 (Node 4 (Node 2 (Node 1 Empty Empty) (Node 3 Empty Empty)) (Node 6 Empty Empty)) (Node 7 Empty (Node 8 Empty Empty))
> size newTree
8