SUNY Geneseo Department of Computer Science

Performance of Tree Searches

Previous Lecture

Questions?

Ordered tree algorithm from lab? How to create unordered trees to test on?

• Hand-build unordered trees

    OrderedTree t = new OrderedTree()
    t.insertNode( new Integer(5) )
    t.getLeft().insertNode( new Integer(10) )
    ....

• vs addNode(...) which forces tree to be ordered

Performance of Search-Style Algorithms

Section 13.3.5

Search time depends on height more than number of items

Fully balanced tree has two children at every node in every non-leaf level, both subtrees fully balanced and of same height

• Every root-to-leaf path exists and is of same length
• height = log₂(n+1)
• = execution time for search (worst case)

Tree of height h, worst-case search time = Θ(h)

What if tree is totally unbalanced?

Search time in terms of n

• Best case: Θ(1)
• Best worst case (balanced tree): Θ(logn)
• Worst worst case (completely unbalanced): Θ(n)

Decision Trees

Trees used to classify things - useful model for complex conditionals, AI, etc.

What can you say about how fast a decision tree with n possible outcomes can make a decision?

• Similar to time to search to a leaf in ordered tree
• Because decision algorithm looks like it will run in time Θ(h)

Height of tree in terms of number of leaves

• "Some kind of log₂(number of leaves)"
• log2(n-1) for n leaves?

Work it out

Reading said one more leaf than non-leaf nodes for fully-balanced trees

• For m nodes, h = log₂(m+1)
• n leaves
• p non-leaves, p = n-1
• m = n + n - 1 = 2n - 1
• So h = log₂( 2n )
• = log₂( n ) + log₂2
• = log₂( n ) + 1

Decision time Θ(h) = Θ( log₂n + 1 )

• = Θ( log n )
• In fully balanced tree

Other extreme? completely unbalanced tree?

• Time is unbounded

Next

Deletion from ordered trees

section 13.5.1

Next Lecture