CSC148H1 Lecture Notes - Lecture 27: Insertion Sort, Merge Sort, Bubble Sort
CSC148: Lecture 27: Efficiency and Merge Sort
References: Code seen in the pictures can be found on the CSC148 website
http://www.teach.cs.toronto.edu/~csc148h/winter/
Trees and Efficiency
- How efficient is __contains___ in the following cases?
o General tree class
▪ Visit every node
• Linear with number of nodes
o General BTNode class
▪ Visit every node- linear with the number of nodes
o BST class
▪ If tree is “balanced” visit in about lg(n)
Node Packing
- Maximum number of nodes in a binary tree of height:
o 0 -> max = 0
o 1 -> max = 1
o 2 -> max = 3
o 3 -> max = 7
o 4 -> max = 15
- For a given number of nodes n the maximum height of the tree = 2h – 1
o So n <= 2h – 1
o n + 1 <= 2h
o If n < 2h < 2n, take log2 of both sides:
▪ log2(n + 1) <= log2(2h)
▪ log2(n + 1) <= h
▪ h >= log2(n + 1) = h
- If BST is tightly packed (aka balanced), can use proportional to lg(n) time to search n
nodes
- Will search time be proportional to lg(n)?
o Only if tree is balanced
o Searching in unbalanced tree is proportional to n
1
CSC148H1 Full Course Notes
Verified Note
1 document
Document Summary
References: code seen in the pictures can be found on the csc148 website http://www. teach. cs. toronto. edu/~csc148h/winter/ How efficient is __contains___ in the following cases: general tree class, visit every node, linear with number of nodes, general btnode class, visit every node- linear with the number of nodes, bst class. If tree is balanced visit in about lg(n) Maximum number of nodes in a binary tree of height: 0 -> max = 0, 1 -> max = 1, 2 -> max = 3, 3 -> max = 7, 4 -> max = 15. For a given number of nodes n the maximum height of the tree = 2h. 1: so n <= 2h 1, n + 1 <= 2h. If n < 2h < 2n, take log2 of both sides: log2(n + 1) <= log2(2h) log2(n + 1) <= h: h >= log2(n + 1) = h.
