Errata

Data Structures and Algorithms in Java

Michael T. Goodrich and Roberto Tamassia

Preface

• Page vi (thanks to Joseph O'Rourke)
  In the fourth paragraph, replace "feshman-sophomore" with "freshman-sophomore".

Chapter 2

• Code Fragment 2.3 (thanks to Jian Huang)
  Replace "if x <- A[i] then" with "if x = A[i] then"
• Page 45 (thanks to Woody Anderson)
  • In the first equation, replace "5n -1" with "5n".
  • In the second equation, replace "= 7n - 3" with "=7n - 2".
  • In the paragraph beginning with "The best case ...", replace "t(n) = 5n - 1" with "t(n) = 5n" and "t(n) = 7n - 3" with "t(n) = 7n - 2".

Chapter 4

• Page 115 (thanks to Finn Smith)
  In the first sentence of the second paragraph, change "is a called a" to "is called a".
• Code Fragment 4.2 (thanks to Fei Tan)
  Method nodeAtRank(rank) does not work correctly when rank=size(). The else part should be replaced with else { // scan backward from the tail node = trailer; for (int i=0; i < size()-rank ; i++) node = node.getPrev(); }
• Code Fragment 4.3 (thanks to Joseph Leichter)
  The method setNext should be listed under update methods, and not under accessor methods
• Code Fragment 4.4
  Replace "rack" with "rank".

Chapter 5

• Java Code Fragments in Sectiob 5.2 (thanks to Frank Dehne)
  Most Java code fragments in Section 5.2 have small inconsistencies. Please view them as pseudo-code. A revised version will be made available.
• Code Fragment 5.18 (thanks to Joseph Leichter, Ben Master, and Ray Prisament)
  Replace
  "recursively tour the right subtree of v by calling EulerTour(T, T.leftChild(v))"
  with
  "recursively tour the right subtree of v by calling EulerTour(T, T.rightChild(v))"
• Code Fragment 5.27 (thanks to Yusuke Naito and Akimichi Inaba)
  In method isInternal, it is better to replace "||" with "&&". Using "||" is correct but less robust than "&&".
• Chapter Notes
  The Euler tour traversal technique was introduced by Tarjan and Vishkin, motivated by the design of parallel algorithms [R. Tarjan and U. Vishkin, An efficient parallel biconnectivity algorithm, SIAM J. Comput. 14, 862-874 (1985)].

Chapter 6

• Figure 6.5 (thanks to Ming-En Cho and Keith Schmidt)
  The blue node in part (a) should contain the item (8,W).
• Code Fragment 6.1 (thanks to Keith Schmidt)
  The second while loop should read: while P is not empty do e <- P.removeMinElement() {remove a smallest element from P} S.insertLast(e) {add the element to the end of S}
• Page 314 (thanks to Keith Schmidt)
  In the specification of method isEqual(B), replace "Input: Two set objects;" with "Input: Set;"
• Page 327 (thanks to Keith Schmidt)
  In the right hand side of the equation defining s_i(n), replace "n-2ⁱ-1" with "n-(2ⁱ-1)"

Chapter 7

• Code Fragment 7.4 (thanks to Joseph Leichter)
  The implementation of method findElement is incorrect. Statement return key(pos); should be replaced with return element(pos);
• Code Fragment 7.5 (thanks to Adam Leventhal)
  The implementation of method remove is incorrect for the case when the key is at a node with internal children. The item at position parent(remPos) should replace the item at position swapPos before removeAboveExternal(remPos) is performed.
• Code Fragments 7.4-7.5 (thanks to Joseph Leichter)
  The instance variable actionPos is meant to be used by classes extending SimpleBinarySearchTree to identify the position where the previous search, insertion, or deletion has taken place. Position actionPos has the intended meaning provided it is used right after executing methods findElement, insertItem or remove on the superclass.
• Figure 7.9 (thanks to Keith Schmidt)
  In parts (b) and (d), the left-to-right order of the subtrees should always be T₀, T₁, T₂, T₃.
• Page 287 (thanks to Woody Anderson)
  In the definition of the hash function h(k)=(ak+b) mod N, parameter a should be chosen such that a mod N != 0.

Chapter 8

• Figure 8.9 (thanks to Chris Morley)
  In parts (f) and (g), the indices l and r should be exchanged, since the swap with the pivot is performed after the indices cross.
• Page 335 (thanks to Michael Fried)
  The last line of the first paragraph should read
  "Randomized quick-select is described in Code Fragment 8.9."

Chapter 12

• Page 479 (thanks to Finn Smith)
  In line 8 of the first paragraph, replace "parition" with "partition".

Chapter 13

• Page 534 (thanks to Mark Handy)
  Regarding the depth property of a red-black tree, note that the ancestors of a node of a tree include the node itself (see the definitions on trees in Section 5.1.1). Thus, in Fig. 13.8, all the external nodes have 4 black ancestors.
• Page 536 (thanks to Mark Handy and Rebecca Sun)
  The description of the insertion algorithm should consider the case of an insertion into an empty red-black tree (i.e., a red-black tree consisting of a single external node). To take this case into account, replace the sentence
  "We color z red and its children black."
  with
  "If z is the root of T, we color z black, else we color z red. Also, we color the children of z black."
  and replace the sentence
  Indeed, if the parent v of z is red, ..."
  with
  Indeed, if z is not the root of T and the parent v of z is red, ..."
  Note that Code Fragment 13.1 correctly takes this special case into account.
• Figure 13.10 (thanks to Mark Handy)
  In the top two structures of part (a), the left-to-right order of the keys stored at the nodes should be reversed.
• Page 542 (thanks to Mark Handy)
  The description of the deletion algorithm should consider the case when the node v storing the item to remove is red and has an external child w. To take this case into account, replace
  "If r is red, we color it black and we are done."
  with
  "If v was red (and thus r is black), or if r is red (and thus v was black), we color r black and we are done."
• Figure 13.17 (thanks to Russell Cole)
  In part (b), node x should be colored blue (indicating a red node) and node y should be colored black (indicating a black node).

Chapter 15

• Code Fragment 15.2 (thanks to Keith Schmidt)
  
  • In the if test, replace "point(prev)" with "(point(prev)".
  • In the last line, replace "S.remove(last())" with "S.remove(S.last())" and "duplicate copy" with "copy".

Appendix A

• Page 698 (thanks to Jian Huang)
  In the definition of class HashPoint, replace public hashPoint (int x, int y) with public HashPoint (int x, int y)

Appendix B

• Proposition B.2 (thanks to Jack Snoeyink)
  The inequality holds only for x > -1.
• Proposition B.3 (thanks to Jack Snoeyink)
  The upper bound (<=) holds only for x < 1.
• Proposition B.4 (thanks to Jack Snoeyink)
  The upper bound (<=) does not hold, e.g., for x = -n.