Complete Binary tree(CBT) and Almost Complete Binary tree(ACBT): Total nodes and formulae :

-
Connect with me on
Instagram        Twitter           LinkedIn             my website                facebook          Whatsapp             gmail

  Important  about CBT(complete binary tree) & ACBT(Almost complete binary tree)

let : k = level of tree, n = total nodes, ^ is power 

  • total nodes in CBT : 2(k-1)   
  • total nodes n : n =  2(k) – 1
  • in kth level CBT :    
                                leaf nodes  : (n/2) + 1;

                                 non leaf nodes : (n/2);
  • in CBT i k level , n nodes then :   
                           n  = 2(k) – 1  
                          n + 1 = 2(k) 
taking log both side with base 2 , 
                         k = Log2(n);
  • in a 10 level CBT : 
                            maximum nodes : 1023 (2(k) – 1)
                            minimum node :   1023 (2(k) – 1)


  • in a 10 level ACBT :
                        maximum nodes :   1023 (2(k) – 1)
                         minumum nodes : 512 
                        explanation :  first select the 9 levels i.e 511 (2(9) – 1)
                                                 then add  1 node that is present in 10th level .
                                                    so 511 +1 = 512 nodes

calculate using the following code  in the jdoodle ide :










Comments

Post a Comment

Popular posts from this blog

PERFECT SQUARE asked by MountainBlue

-
                                                              Perfect Square                                                         Problem Statement You're given an array A of size N, the task is to remove all the elements from the array except perfect squares of any integer and print the updated ay For example, if the given array is 9 12 16. Here, 9 and 16 are the perfect square of numbers 3 and 4 respectively. After removing others from the the t  Input Format: The input consists of two lines:  The first line contains an integer N denoting the size of an array A. The second line contains N integers separated by space denoting elements of the array A. The input will be read from ...
Read more

Harry and Porter asked in MountainBlue ,2022

-
                                                          Problem Statement   Harry and Potter choose a word string. Harry chose a number M  (less than the length of the string) and Potter chose N (less than the length of the string).  Harry will cut M letters from the end of the string, add them to the beginning and will give it to Potter. Then, Potter will also cut N letters from the end of the string,  add it to the beginning and give it to Harry. This process will continue till they get the original word string back.  For a given string and given values of M and N, find the number of turns in which they will get the original word string back . Example If the string is AbcDef, M= 1 and N = 2 the Output must be 4 4604  Explanation This is how the words tend will change. Abcbef > fAbcDe Dejbes- cDefAb AbcDef As...
Read more

Chomsky's hierarchy Explanation :

-
Image
                      Chomsky's hierarchy  Explanation  and its types : Connect with me on According to Chomsky, there are 4 types of Finite language. T0,T1,T2,T3. Chomsky's hierarchy  Diagram: T0 is superset of T1,T2,T3. T1 IS SUPERSET OF T2,T3. T2 IS SUPERSET OF T3. connect with me on A Topic from Theory of Computation (TOC) Chomsky's hierarchy Explanation Table: Language type Accepted Language Accepting machine T3 REGULAR LANGUAGE FINITE AUTOMATA T2 CONTEXT FREE LANGUAGE (CFL) PUSH DOWN AUTOMATA (PDA) T1 CONTEXT SENSETIVE LANGUAGE (CSL) LINEAR BOUND AUTOMATA (LBA) T0 RECURSSIVE ENUMERABLE LANGUAGE (REL) TURING MACHINE Knowledgable Ti...
Read more