Inserção numa BST - Revision history

Root: Inserção numa BST moved to Inserção numa BST

2008-11-12T08:38:32Z

Inserção numa BST moved to Inserção numa BST

← Older revision	Revision as of 08:38, 12 November 2008
(No difference)

Root: /* Inserção na Raiz */

2005-05-19T08:18:27Z

Inserção na Raiz

← Older revision		Revision as of 08:18, 19 May 2005
Line 44:		Line 44:
	== Inserção na Raiz ==		== Inserção na Raiz ==

	link insertT(link h, Item item) {		link '''insertT'''(link h, Item item) {
	Key v = key(item);		Key v = key(item);
	if (h == z) return NEW(item, z, z, 1);		if (h == z) return NEW(item, z, z, 1);
	if (less(v, key(h->item))) {		if (less(v, key(h->item))) {
	h->l = insertT(h->l, item); h = rotR(h);		h->l = '''insertT'''(h->l, item);
			h = '''rotR'''(h);
	}		}
	else {		else {
	h->r = insertT(h->r, item); h = rotL(h);		h->r = '''insertT'''(h->r, item);
			h = '''rotL'''(h);
	}		}
	return h;		return h;
Line 60:		Line 62:
	Implementação da função <code>STinsert</code> do ADT tabela de sÃmbolos.		Implementação da função <code>STinsert</code> do ADT tabela de sÃmbolos.

	void STinsert(Item item) {		void '''STinsert'''(Item item) {
	return head = insertT(head, item);		return head = '''insertT'''(head, item);
	}		}

Root at 08:17, 19 May 2005

2005-05-19T08:17:24Z

@@ Line 1: / Line 1: @@
 Função de inserção recursiva numa BST.
@@ Line 9: / Line 13: @@
      return h;
+   }
 Implementação da função <code>STinsert</code> do ADT tabela de sÃmbolos.
@@ Line 16: / Line 22: @@
+   }
-Implementação não recursiva da função <code>STinsert</code>.
+== Versão Não Recursiva ==
    void '''STinsert'''(Item item) {
@@ Line 32: / Line 40: @@
      x = NEW(item, z, z, 1);
      if (less(v, key(p->item))) p->l = x; else p->r = x;
+   }

Root at 08:13, 19 May 2005

2005-05-19T08:13:54Z

New page

Função de inserção recursiva numa BST.

link '''insertR'''(link h, Item item) {
Key v = key(item), t = key(h->item);
if (h == z) return NEW(item, z, z, 1);
if less(v, t) h->l = '''insertR'''(h->l, item);
else h->r = '''insertR'''(h->r, item);
h->N++;
return h;
}

Implementação da função <code>STinsert</code> do ADT tabela de sÃmbolos.

void '''STinsert'''(Item item) {
head = '''insertR'''(head, item);
}

Implementação não recursiva da função <code>STinsert</code>.

void '''STinsert'''(Item item) {
Key v = key(item);
link p = head, x = p;
if (head == z) {
head = NEW(item, z, z, 1);
return;
}
while (x != z) {
p = x;
x->N++;
x = less(v, key(x->item)) ? x->l : x->r;
}
x = NEW(item, z, z, 1);
if (less(v, key(p->item))) p->l = x; else p->r = x;
}