Mathematical Properties of Binary Trees
Not what you're looking for?
-----------
Show that if binary tree T is full at level i, then it is full at every level j smaller than i.
---------------
Show that the depth of the complete binary tree Tn for a general n is given by
D(Tn) = [log2n].
See attached for better format.
------------
Using induction, give a direct proof of Proposition 4.2.3 without using the transformation to 2-trees.
Proposition 4.2.3
Suppose T is any 2-tree. Then the number of leaf nodes is 1 greater than the number of internal nodes of T; that is,
I(T) = L(T) - 1.
Equivalently, we have
n(T) = 2L(T) - 1.
----------
Prove Proposition 4.2.5
Proposition 4.2.5
Suppose T is a 2-tree. Then T is full at the second deepest level if and only if all the leaf nodes are contained in two levels (d - 1 and d).
-------------
Textbook: Algorithms: Sequential, Parallel, and Distributed by Kenneth Berman and Jerome Paul
Purchase this Solution
Solution Summary
Mathematical Properties of Binary Trees are studied.
Solution Preview
Please see the attached file.
Sol (1).
l(T) = number of internal nodes in T
L(T) = number of leaf nodes in T
If a tree contains a single node, then
l(T) = 0
L(T) = 1
Hence , l(T) = L(T) -1 is true......(i)
Now, let l(T) = L(T) - 1 is true for m leaf nodes.
So, L(T) = m
l(T) = m -1
Now, we add 2 Childs to a leaf node. So, number of leaf node is decreased by 1 and increased by 2. Also, number of internal node is increased by 1.
Hence, L(T) = (m - 1) + 2 = m + 1
l(T) = ( m -1 ) + 1 = m
So, again l(T) = L(T) -1
Hence, whenever l(T) = L(T) - 1 is true for m leaf nodes, it is also true for m+1 leaf nodes. So we can say that l(T) = L(T) -1 is always true for any number of leaf nodes in the tree.
Also total number of nodes = internal nodes + leaf nodes
n(T) = l(T) + L(T)
n(T) = L(T) + L(T) - 1
n(T) = ...
Purchase this Solution
Free BrainMass Quizzes
Basic Computer Terms
We use many basic terms like bit, pixel in our usual conversations about computers. Are we aware of what these mean? This little quiz is an attempt towards discovering that.
Javscript Basics
Quiz on basics of javascript programming language.
Inserting and deleting in a linked list
This quiz tests your understanding of how to insert and delete elements in a linked list. Understanding of the use of linked lists, and the related performance aspects, is an important fundamental skill of computer science data structures.
Word 2010: Tables
Have you never worked with Tables in Word 2010? Maybe it has been a while since you have used a Table in Word and you need to brush up on your skills. Several keywords and popular options are discussed as you go through this quiz.
Basic UNIX commands
Use this quiz to check your knowledge of a few common UNIX commands. The quiz covers some of the most essential UNIX commands and their basic usage. If you can pass this quiz then you are clearly on your way to becoming an effective UNIX command line user.