(→Outras Funções do ADT) |
(→Outras Funções do ADT) |
||
Line 29: | Line 29: | ||
* <code>STinsert</code> - | * <code>STinsert</code> - | ||
− | * <code>STsearch</code> - | + | * <code>STsearch</code> - [[Procura numa BST|pesquisa um elemento dada a sua chave]] |
* <code>STdelete</code> - | * <code>STdelete</code> - | ||
* <code>STselect</code> - [[Selecção da k-ésima Menor Chave (BST)|selecção da k-ésima menor chave]] | * <code>STselect</code> - [[Selecção da k-ésima Menor Chave (BST)|selecção da k-ésima menor chave]] | ||
* <code>STsort</code> - | * <code>STsort</code> - |
Dependências da implementação do ADT tabela de sÃmbolos baseado em BSTs. A árvore está ancorada em head
e as folhas são nós vazios (representados por z
): assim, os algoritmos apenas manipulam nós internos da árvore.
#include <stdlib.h> #include "Item.h" typedef struct STnode* link; struct STnode { Item item; link l, r; int N }; static link head, z;
Esta função não faz parte da interface do ADT. A ideia subjacente é isolar procedimentos repetitivos da criação de novas entradas da BST.
link NEW(Item item, link l, link r, int N) { link x = (link)malloc(sizeof *x); x->item = item; x->l = l; x->r = r; x->N = N; return x; }
void STinit() { head = z = NEW(NULLitem, 0, 0, 0); } int STcount() { return head->N; }
STinsert
- STsearch
- pesquisa um elemento dada a sua chaveSTdelete
- STselect
- selecção da k-ésima menor chaveSTsort
-