Tree project

**<1>depth and no. of entries**

depth max no. of level

the min no. of nodes to reach depth d for a heap

= 1 + 2 + 4 +....+ 2^{d-1} + 1

= 2^{d}

since

the total no. of nodes n

>= the min. no. of nodes to reach depth d

==> n >= 2^{d}

==> log_{2} n >= d

**<2> Worst-case Times for tree operations**

The worst-case time performance for the

following operations are all O(d) . d : depth of tree

- adding an entry in a binary search tree,

heap or a B-tree. - deleting an entry in a binary search tree,

heap or a B-tree. - searching for a specific entry in a binary

search tree or a B-tree.

**Note : **

- the smaller the depth is the more the

efficiency is. That is why heap and

B-tree are more efficient compared to other. - O(d) = O(log
_{2}n) - Logarithmic algorithm are algorithm with

worse-case time O (log_{2}n)

n ==> log_{2} n

2n ==> log_{2} n + 1