implement extract_min (removes least element) on an unbalanced binary search tre

Question

implement extract_min (removes least element) on an unbalanced binary search tree in a persistent way. C++ or puescode is fine.

Explanation / Answer

T findEQ(T x) { Node u = r; while (u != nil) { int comp = compare(x, u.x); if (comp < 0) u = u.left; else if (comp > 0) u = u.right; else return u.x; } return null; } T find(T x) { Node w = r, z = nil; while (w != nil) { int comp = compare(x, w.x); if (comp < 0) { z = w; w = w.left; } else if (comp > 0) { w = w.right; } else { return w.x; } } return z == nil ? null : z.x; } boolean add(T x) { Node p = findLast(x); return addChild(p, newNode(x)); } Node findLast(T x) { Node w = r, prev = nil; while (w != nil) { prev = w; int comp = compare(x, w.x); if (comp < 0) { w = w.left; } else if (comp > 0) { w = w.right; } else { return w; } } return prev; } boolean addChild(Node p, Node u) { if (p == nil) { r = u; } else { int comp = compare(u.x, p.x); if (comp < 0) { p.left = u; } else if (comp > 0) { p.right = u; } else { return false; } u.parent = p; } n++; return true; }

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.