O'Reilly logo

Art of Computer Programming, The: Volume 3: Sorting and Searching by Donald E. Knuth

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

Section 6.2.2

1. Use a header node, with say ROOTRLINK(HEAD); start the algorithm at step T4 with PHEAD. Step T5 should act as if K > KEY(HEAD). [Thus, change lines 04 and 05 of Program T to ‘ENT1 ROOT; CMPA K’.]

2. In step T5, set RTAG(Q) ← 1. Also, when inserting to the left, set RLINK(Q)P; when inserting to the right, set RLINK(Q)RLINK(P) and RTAG(P) ← 0. In step T4, change the test “RLINK(P)Λ” to “RTAG(P) = 0”. [If nodes are inserted into successively increasing locations Q, and if all deletions are last-in-first-out, the RTAG fields can be eliminated since RTAG(P) will be 1 if and only if RLINK(P) < P. Similar remarks apply with simultaneous left and right threading.]

3. We could replace Λ by a valid address, and set KEY( ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required