| Current Forum: 15-211 Main Forum |
| Date: Wed Dec 19 2001 9:59 am |
| Author: White, David <white3@andrew.cmu.edu> |
| Subject: Q, 4 Fall 99, heap, balanced tree |
|
|
In the book on p. 119 it says all operations on AVL
trees (balanced trees) can be done in O(Log(N)) EXCEPT
possibly insertion. It never says insertion can be done in O(LOG(N)) but can it? The answer for Q 4. B says it can...
Also, for part A, why isn't a heap included in the answer? A heap is a complete balanced tree, and can be even perfect, so why can't it do member, insert and remove on O(log(n))? It says insert and deletemin are O(LogN) and it is a good tree so why can't find be done in O(LogN)?
Thanks! |
|