Buy GNU books!
|[ < ]||[ > ]||[ << ]||[ Up ]||[ >> ]||[Top]||[Contents]||[Index]||[ ? ]|
1. Yes. Both code segments update the nodes along the direct path from y down to n, including node y but not node n. The plain AVL code excluded node n by updating nodes as it moved down to them and making arrival at node n the loop's termination condition. The PAVL code excludes node n by starting at it but updating the parent of each visited node instead of the node itself.
There still could be a problem at the edge case where no nodes' balance factors were to be updated, but there is no such case. There is always at least one balance factor to update, because every inserted node has a parent whose balance factor is affected by its insertion. The one exception would be the first node inserted into an empty tree, but that was already handled as a special case.
2. Sure. There is no parallel to Exercise 5.4.4-4 because q is never the pseudo-root.
|webmaster donations bookstore||delorie software privacy|
|Copyright © 2003 by The Free Software Foundation||Updated Jun 2003|