C++: binary search trees have their best performance when they are balanced, whi

Question

C++: binary search trees have their best performance when they are balanced, which means that at each node n, the size the size of the left subtree of n is within one of the size of the right subtree of n. Write a function that takes a sorted linked list of entries and produces a balanced binary search tree. If useful, you may add extra parameters to the procedure, such as the total number of entries in the list. Hint: first build the left subtree of the root, then the right subtree of the root, then put the pieces together with the join function. Think recursively
Template<class Item> Void join( Bag <item>& top, Bag <item>& left, Bag <item>& right };
Top.root_prt->set_left (left.root_prt) Left.root_prt=Null;
Top.root_ptr->set_right(right.root_ptr); Right.root_prt=null; C++: binary search trees have their best performance when they are balanced, which means that at each node n, the size the size of the left subtree of n is within one of the size of the right subtree of n. Write a function that takes a sorted linked list of entries and produces a balanced binary search tree. If useful, you may add extra parameters to the procedure, such as the total number of entries in the list. Hint: first build the left subtree of the root, then the right subtree of the root, then put the pieces together with the join function. Think recursively
Template<class Item> Void join( Bag <item>& top, Bag <item>& left, Bag <item>& right };
Top.root_prt->set_left (left.root_prt) Left.root_prt=Null;
Top.root_ptr->set_right(right.root_ptr); Right.root_prt=null;
Template<class Item> Void join( Bag <item>& top, Bag <item>& left, Bag <item>& left, Bag <item>& right Bag <item>& right };
Top.root_prt->set_left (left.root_prt) Left.root_prt=Null;
Top.root_ptr->set_right(right.root_ptr); Right.root_prt=null;

Explanation / Answer

class Tree { Tree left, right; static interface Observer { public void before(); public void after(); public boolean end(); } static boolean traverse(Tree t, Observer o) { if (t == null) { return o.end(); } else { o.before(); try { if (traverse(left, o)) return traverse(right, o); return false; } finally { o.after(); } } } boolean balanced() { final Integer[] heights = new Integer[2]; return traverse(this, new Observer() { int h; public void before() { h++; } public void after() { h--; } public boolean end() { if (heights[0] == null) { heights[0] = h; } else if (Math.abs(heights[0] - h) > 1) { return false; } else if (heights[0] != h) { if (heights[1] == null) { heights[1] = h; } else if (heights[1] != h) { return false; } } return true; } }); } }

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

---

---

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