Hi all

Here are two questions from my Algorithms & Complexity Theory assignment.


1. A complete binary tree is a binary tree in which every level, except possibly the deepest, is completely filled. At depth n, the height of the tree, all the nodes must be as far left as possible. The concept of a complete binary tree extends to the concept of a complete k-ary tree in an obvious way, k>=2.

a) Show how a complete k-ary tree can be implemented efficiently using an array.
b) Design and analyze a procedure for inserting an element into a k-ary heap implemented using an array
c) Design and analyze a procedure for deleting an element from a k-ary heap implemented using an array
d) Design and analyze a k-ary heapsort.


2.
http://www.apcx.3rror.com/images/binaryTreeQuestion.JPG
...and determine when the equality is true.