COMP 2402 Chapter Notes - Chapter 8: Binary Search Tree
27 Dec 2014
School
Department
Course
Professor
Document Summary
A scapegoattree keeps itself balanced from partial rebuilding operations. During a partial rebuilding an entire subtree is deconstructed and rebuilt into a perfectly balanced subtree. The node value that"s the median in the original subtree will be the root of the rebalanced subtree void rebuild(node u) { int ns = size(u); Node[ ] a = array. newinstance(node. class, ns); packintoarray(u, a, 0); if (p == nil) { r = buildbalanced(a, 0, ns); r. parent = nil; } else if (p. right == u) { p. right = buildbalanced(a, 0, ns); p. right. parent = p; } else { p. left = buildbalanced(a, 0, ns); p. left. parent = p; int packintoarray(node u, node[ ] a, int i) { if (u == nil) { return i; i = packintoarray(u. left, a, i); a[i++] = u; return packintoarray(u. right, a, i); A call to rebuild(u) takes o(size(u)) time. The resulting subtree has the minimum possible height. 8. 1 scapegoattree: binary search tree with partial rebuilding.
