Lecture 13



I did a quick review of Binary Search Trees. Operations, INSERT, DELETE, FIND, and a traversal to print out the contents of the entire tree. Without rebalancing, a binary search tree may perform rather inefficiently. I briefly mentioned the 3 different re-balancing schemes that are covered in our text book. They are:

AVL trees - efficient but complicated. Deletions and note covered in our book.

Red Black trees - more efficient by a constant factor than AVL trees (in particular for deletions). Deletions not covered in our book. I will not cover this material.

AA trees. Competitive with AVL And Red Black trees. Rebalancing these trees should be easier to explain and understand.

With that in mind I describe 2-3 trees, as the AA trees are a binary tree representation of 2-3 trees. Also B trees which we will also cover are a generalization of 2-3 trees.

I have attached a presentation describing a close relative of 2-3 trees, that is, 2-4 trees. Multiway(2,4).pdf

Readings from chapter 19.

Chapter 19.
19.1 Read
19.1.2 Optional
19.2 Read
19.2.1.Optional
19.3 Read
19.4 Read
19.5 Skip
19.6 Read
19.7 Optional
19.8 Read

Posted: Mon - February 7, 2005 at 04:55 PM        

©