Hey,

The figure overlaps in at-least two place I can see so far:

https://github.com/liuxinyu95/AlgoXY/blob/algoxy/others/preface/preface-en.tex#L353 (Page 17)
https://github.com/liuxinyu95/AlgoXY/blob/algoxy/others/preface/preface-en.tex#L444 (Page 19)

How can it can be corrected? I am not familiar with Tex. I don't know if the figure or content is the problem.

Hi,

This line https://github.com/liuxinyu95/AlgoXY/blob/algoxy/others/appendix/list/list-en.tex#L1835

Not sure why here use a \neg less instead of plain less.

I can't attach images, so here's a link: http://imgur.com/T4AtLr5

That's from section 1.2, the relevant tex file being datastruct/tree/binary-search-tree/bstree-en.tex.

This isn't the only place where I've noticed this problem.

中文版，Chapter 7，第156页。
"除根节点外，将节点个树乘以t − 1"应该是
"除根节点外，将节点个数乘以t − 1"。

在 1.5.3 前驱(Successor)和后继(predecessor)

给定元素x，它的后继元素y是满足y > x的最小值。有两种情况:如果x所 在的节点有一个非空的右子树，则右子树中的最小值就是答案。如图1.5所示， 8的后继元素为9，它是元素8的右子树中的最小值。另外一种情况是，如果x没 有非空的右子树，我们需要向上回溯，找到最近的一个祖先，使得该祖先的左 侧孩子，也为x的祖先。如图1.5所示，元素2所在的节点没有右侧分支，我们向 上回溯一步找到元素1，但是1没有左侧分支，因此需要继续向上查找，这次我 们到达了元素3所在的节点。而3的左侧孩子，同样也是2的祖先。至此，我们找 到了2的后继元素3。

这里查找2的后继，和1的左子树有什么关系？

Summary

On 4/25/2023, we experienced a build break for the PDF book for 3 days. The root cause was because the delayed answers to the exercise exceeded the memory limitation (5M) of XeLaTex in Linux platform. I turned on the option to delay populating answers at the end of the book, LaTex had to cache the answers in memory unless meet a shipoutAnswer command. As I added more answers, the cached content finally could not be held in memory any more (with total 14 chapters, a preface, and 2 appendices). As the mitigation, I temporarily distributed the answers as the last section of each chapter (force shipoutAnswer in every chapter). This prevented memory bloating, but the reading experience is supplement to have all answers together after the main content. I am working on a long-term solution to this issue.

Timeline

• On 4/25: A new answer about DFS Maze solution with stack caused delayed answer exceeded XeLaTex limit, causing build break in github workflow.
• After hours, I received build break notification. From the build log, it was out of memory. I randomly reduced some label/refs, and questions in exercise/answers. But it didn't work;
• On 4/26: I though the out of memory issue might be caused by big tikz/pgf figures. Followed recommendation, I tried externalize tikz/pgf figures. It reduced some memory, but still exceeded finally.
  In prelude.stl:

\usetikzlibrary{external,patterns,matrix,positioning,shapes,arrows}
\tikzexternalize[prefix=img/]

In Makefile:

TEX_FLAGS = -shell-escape
%.pdf: %.tex; latexmk -cd -xelatex $(TEX_FLAGS) $<

• I tried to switch from XeLaTex to LuaLaTex as it can dynamically allocate memories. However, I realized it need more change as the xeCJK pkg can't work with LuaLaTex. I need a quick mitigation.
• On 4/27, I established a cloud desktop in Linux, with the latext TeXLive, split out fix-linux-bb branch, tried to reproduce the issue.
• I found the eps files can't be recognized well in the TeXLive version. I replaced most eps figures with PNG (exported from drawio) in chapter 14, and found that the last chapter could be build standalone successfully. The build break only happened to the entire book build.
• I applied 'binary search' to comment out newly added answers, but didn't find any infinite populated content.
• Finally, I came to the question: 'How does the delayed answer work?' After check the exercise pkg doc, I found this:

More precisely, the answers are stored in a vertical box. When \shipoutAnswer is encountered, this box is emptied and its contents is placed in the main vertical list.

• At this point, I realized as I added more exercise/answers it will eventually exceed memory in the future with this settings.
• I forced a shipoutAnswer in chapter 13, build pass.
• I temporarily distributed answers to each section.

Future Solution

Given it's my plan to add more and more exercise/answers. Current 'delayed answer' approach is not scale with any fixed memory settings. If we want to achieve the good reader experience of continued main content, the long-term solution is to switch to LuaLaTex. However, this need careful changes, because:

1. CTex depends on xeCJK, but the community decided not to port CJK to LuaLaTex, but adopted luatexja, see this.
2. I have different default font settings for CN/EN on each OS (e.g., STSong in Mac OS X, Noto CJK for Linux, and SimSun for Windows). They depend on setCJKXxxFont.

I am going to take stepped approach to iteratively make this change:

1. Create a LuaTex branch to separate this migration from XeTeX to LuaTeX (will clean up some legacy branches);
2. Create a MacOSX branch to go on adding answers to chapter 14, As the memory quota in Mac is still enough. With this branch, I can complete the book as soon as possible;
3. Later merge the master branch (algoxy) with the above two.

Besides, I'll also explore better solution to secure figure quality (may be SVG is better than PNG) with reasonable size overhead.

--
Xinyu

if the buffer size = 1, head and tail always 0,
so we can't use head == tail to judge if the queue is empty,

中文版，Chapter 8，第196页。
“如果k是一个最小堆的顶部元素，所有左右子树中的元素都小于k。“ 应该是
“如果k是一个最小堆的顶部元素，所有左右子树中的元素都大于k。”

根据4.1中平衡因子的定义，为|L| - |R|
但在4.11中平衡因子的定义为equals to the difference from the right sub tree and left sub tree, 且后面的解释都以此为准
请问是应该以哪个定义为标准？

如题

Version: 0.6180339887498949

Version: 0.6180339887498949

原文：

图4.7给出了两棵红黑树。它 们分别由序列 11, 2, 14, 1, 7, 5, 8, 4 和 1, 2, ..., 8 构建而成。

问题：
4.7左图有数字“15”，原文叙述中没有提到“15”

我用这个序列：“15, 14, 11, 2, 1, 7, 5, 4, 8” 构造出了4.7左图
测试工具：

There are 2 main issues with the AVL tree in the first edition:

• There are no AVL tree deletion algorithms. The deletion algorithms are left as Exercise to the reader, which caused negative Reader experience[1];
• The formal proof to the AVL tree insertion pattern matching algorithm isn't necessarily to be explained in the main chapter. It caused to the poor Reader experience.

Here are the action items to address this issue:

• Add a new appendix about AVL tree, move the proof part to the appendix;
• Add deletion algorithms in both functional and imperative approaches to the appendix.

--
[1]. comment by descent in http://www.ituring.com.cn/book/1907

dot -Gsize="8,10.5" -Tps -o q2.ps q2.dot
Warning: flat edge between adjacent nodes one of which has a record shape - replace records with HTML-like labels
Edge x1 -> x2
Error: lost x1 x2 edge
Error: lost x2 x3 edge
make[2]: *** [q2.ps] Error 1
make[1]: *** [image] Error 2

Preface，练习一，第1题中：

之后再次扫描一遍列表，找到第一个整数所在的位置就是答案。

似应为“找到第一个正数所在的位置”。

"V.S." is incorrect, as "vs." is the abbreviation of the Latin word versus.

其实你这本书内容还不错，为什么不把他写成中文呢？(不要误会我的意思，我英文水平还行)

请问是否能改进一下排版。这本书是以电子书形式发布的，但是排版却是印刷书的格式。譬如：1. 页边距过大，如果设为1inch左右比较好。 2. 页面是two-sided格式（奇数页往左倾，偶数页右倾），非印刷书籍这个似乎不需要。我觉得类似http://theory.stanford.edu/~tim/f13/f13.pdf 这样的格式似乎更易阅读。

在0.3.1章的算法中，GET-NUMBER(n)这个函数里面，x没有自增，应改为

\Function{Get-Number}{$n$}
  \State $x \gets 0$
  \State $i \gets 0$
  \Loop
    \If{\Call{Valid?}{$x$}}
      \State $i \gets i + 1$
      \If{$i = n$}
        \State \Return $x$
      \EndIf
    \EndIf
    \State $x \gets x + 1$
  \EndLoop
\EndFunction

为什么没有红黑树的c++实现代码，但是书中又说有的？

What if you split the the list more than two and use more tasks?
It appears in chapter 3, first exercise, Red black trees.

I think you need to use the right data structure for DFS.

If you change queue to deque, and visit to set you can speed it up by near 40x:

Here is the code:

from collections import deque

START = [[(1, 1), (2, 1)],
         [(1, 4), (2, 4)],
         [(3, 1), (4, 1)],
         [(3, 2), (3, 3)],
         [(3, 4), (4, 4)],
         [(5, 1)], [(4, 2)], [(4, 3)], [(5, 4)],
         [(1, 2), (1, 3), (2, 2), (2, 3)]]

class Node:
    def __init__(self, l, p = None):
        self.layout = l
        self.parent = p

def solve(start):
    global visit
    visit = set([normalize(start)])
    queue = deque([Node(start)])
    while queue:
        cur = queue.popleft()
        layout = cur.layout
        if layout[-1] == [(4, 2), (4, 3), (5, 2), (5, 3)]:
            return cur
        else:
            for brd in expand(layout, visit):
                queue.append(Node(brd, cur))
                visit.add(normalize(brd))
    return None # no solution

def expand(layout, visit):
    def bound(y, x):
        return 1 <= y and y <= 5 and 1 <= x and x <= 4
    def valid(m, i, y, x):
        return m[y - 1][x - 1] in [0, i]
    def unique(brd):
        mn = (normalize(brd), normalize(mirror(brd)))
        return not visit.intersection(mn)
    s = []
    d = [(0, -1), (0, 1), (-1, 0), (1, 0)]
    m = matrix(layout)
    for i in range(1, 11):
        for (dy, dx) in d:
            if all(bound(y + dy, x + dx) and valid(m, i, y + dy, x + dx)
                    for (y, x) in layout[i - 1]):
                brd = move(layout, (i, (dy, dx)))
                if unique(brd):
                    s.append(brd)
    return s

def dup(layout):
    return [r[:] for r in layout]

def matrix(layout):
    m = [[0]*4 for _ in range(5)]
    for (i, ps) in zip(range(1, 11), layout):
        for (y, x) in ps:
            m[y - 1][x - 1] = i
    return m

def move(layout, delta):
    (i, (dy, dx)) = delta
    m = dup(layout)
    m[i - 1] = [(y + dy, x + dx) for (y, x) in m[i - 1]]
    return m

def mirror(layout):
    return [[(y, 5 - x) for (y, x) in r] for r in layout]

def normalize(layout):
    return tuple(sorted(tuple([tuple(sorted(r)) for r in layout])))

# pretty print
def output(node):
    seq = []
    while node is not None:
        seq = [node.layout] + seq
        node = node.parent
    for layout in seq:
        for r in matrix(layout):
            print ["%X" % x for x in r]
        print "\n",
    print "total", len(seq) - 1, "steps"

if __name__ == "__main__":
    output(solve(START))

-- Insert an element into a tree
insert::(Ord a) => Tree a -> a -> Tree a
insert Empty k = Node Empty k Empty
insert (Node l x r) k | k < x = Node (insert l k) x r
                      | otherwise = Node l x (insert r k)

delete::(Ord a)=> Tree a -> a -> Tree a
delete Empty _ = Empty
delete (Node l k r) x | x < k = (Node (delete l x) k r)
                      | x > k = (Node l k (delete r x))
                      -- x == k
                      | isEmpty l = r
                      | isEmpty r = l
                      | otherwise = (Node l k' (delete r k')) where k' = min r

-- in-order tree traverse
mapT::(a->b) -> Tree a -> Tree b
mapT _ Empty = Empty
mapT f (Node l x r)= Node (mapT f l) (f x) (mapT f r)


-- Traverse a part of tree inside a range [a, b]
mapR :: (Ord a)=>(a->b) -> a -> a -> Tree a -> Tree b
mapR f a b t = map' t where
    map' Empty = Empty
    map' (Node l k r) | k < a = map' r
                      | a <= k && k <= b = Node (map' l) (f k) (map' r)
                      | k > b = map' l
               

这里节点值和参数 k 和 x 没有统一，时不时互换含义使用。除此之外还有好几个函数也是这样颠倒了。

第六章后缀树 6.4.4 查找最长回文提到了一种算法

如果字符串S的某个子串w是一个回文,则w一定也是reverse(S)的子串。例 如“issi”是“mississippi”的子串,同时它也是反转的字符串“ippississim”的子串。
根据这一点,我们可以通过寻找S和reverse(S)的最长公共子串来获得最长回文。

palindromem(S) = LCS(suffixTree(S ∪ reverse(S)))

这个方法实际上是有bug的，比如有一个字符串S =ABXYBA,reverse(S) = ABYXBA,他们的最长公共子串是AB或者BA,但这明显不是一个回文，当一个字符串包含它的某个子字符串的reverse的时候，用这个方法会有问题。这种情况的修复办法是检查子串区间,S和reverse(S)的AB和BA子串区间都是[0:2]和[4:6]，此时这并不是一个回文子串。

看另一种状况，比如 S = ABAD, reverse(S) = DABA, 他们的公共子串ABA的下标区间在S和reverse(S)中就是不同的，所以这个是一个回文子串.

由于所有的NIL节点都是黑色的，我们通常将NIL节点隐藏不画出，如图\ref{fig:rbt-example-with-nil}所示。

应为：

由于所有的NIL节点都是黑色的，我们通常将NIL节点隐藏不画出，如图**\ref{fig:rbt-example}**所示。

4.1定义一节中，红黑树满足5条性质，有：

\item 所有叶节点（NIL）为黑色。

这里叶节点是指没有数据的NIL节点。

4.2插入一节中，公式（4.5）后有：

如果树为空，我们为 k 创建一个红色叶子节点；

这里的叶子节点应该是指隐藏NIL节点的红黑树表示中的叶子节点，即实际上创建的是带两个NIL子节点的中间节点。因为，在4.2节第一段中，有：

插入时，我们令新节点为红色。只要它不是根节点，除了第四条外的所有性质都可以满足。

如果新节点是带NIL节点表示中的叶子节点（即它不带NIL为子），由于新插入节点为红色，上述红黑树性质并不满足。

所以，我感觉这里明确一下会更好，能够和图示与算法更好地一致。图4.6“插入后需要修复的四种情况”的示例和公式（4.3）的模式匹配表述中，新插入节点都是带有子节点的。我开始在这里迷惑了很久，去网上查了一些2-3-4树和红黑树的讲解才明白过来。

也就是说，在红黑树中，所有带数据的节点都是中间节点，它必定有两个子，或为子树，或为NIL节点。

I want to contribute counting sort

There is no example code for AVL tree in C/C++

在运行

make

之后出现报错

make -C img
make[1]: Entering directory '/tmp/temp_downloads/AlgoXY/img'
convert fibonacci-spiral.png fibonacci-spiral.eps
convert-im6.q16: iCCP: profile 'ICC profile': 'RGB ': RGB color space not permitted on grayscale PNG `fibonacci-spiral.png' @ warning/png.c/MagickPNGWarningHandler/1667.
convert-im6.q16: attempt to perform an operation not allowed by the security policy `EPS' @ error/constitute.c/IsCoderAuthorized/408.
make[1]: *** [Makefile:25: fibonacci-spiral.eps] Error 1
make[1]: Leaving directory '/tmp/temp_downloads/AlgoXY/img'
make: *** [Makefile:51: image] Error 2

请问如何修复该问题

公式（1.7）前：

\item 如果$Y$中仅含有一个元素$[x_n]$，则倒数第$i$个元素就是表头$x_n$；

似应为“则倒数第$i$个元素就是表头**$x_1$**；”

公式（1.7）后：

其中数函$slide(X, Y)$同时丢弃两个列表的头部：

“数函”应为函数

I was wondering if you'd be open for PR's containing source code for additional languages. I'd love to contribute solutions written in JS. Thanks!

Hi @liuxinyu95 ,
Thanks for this open-source algorithm book. I am reading it and find an incorrect if statement condition in Insertion Sort Improvement 2.

\begin{algorithmic}
\Function{Insert}{$L, x$}
  \State $p \gets$ NIL
  \State $H \gets L$
  \While{$L \neq$ NIL $\land $ \Call{Key}{$L$} $<$ \Call{Key}{$x$}}
    \State $p \gets L$
    \State $L \gets $ \Call{Next}{$L$}
  \EndWhile
  \State \Call{Next}{$x$} $\gets L$
  \If{$p \neq$ NIL}                           // It should be \If{$p \eq$ NIL}, right?
    \State $H \gets x$
  \Else
    \State \Call{Next}{$p$} $\gets x$
  \EndIf
  \State \Return $H$
\EndFunction
\end{algorithmic}

Best Regards,

“0.2.3 队列”节：

如果$x$是从$Q_{23}$取出的，我们只将$3x$加入$Q_{23}$，$5x$加入$Q_{235}$。我们不应该将$2x$加入$Q_2$，因为$Q_3$中不允许包含被3整除的数。

应为：
如果$x$是从$Q_{23}$取出的，我们只将$3x$加入$Q_{23}$，$5x$加入$Q_{235}$。我们不应该将$2x$加入$Q_2$，因为**$Q_2$**中不允许包含被3整除的数。

感觉乱了。

\be
%\resizebox{\textwidth}{!}{\ensuremath{
\begin{array}{rcl}
\text{...} & & \

fixB^2\ \mathcal{C}\ a_{\mathcal{B}^2}\ x\ (\mathcal{B}, b, y, c) & = & shiftB\ (\mathcal{C}, (shiftB\ a), x, (\mathcal{R}, b, y, c)) \

fixB^2\ \mathcal{C}\ (\mathcal{B}, a, x, b)\ y\ c_{\mathcal{B}^2} & = & fixB^2\ \mathcal{B}\ a\ x\ (fixB^2\ \mathcal{R}\ b\ y\ c) \

fixB^2\ \mathcal{C}\ l\ k\ r\ & = & (\mathcal{C}, l, k, r) \
\end{array}
%}}
\label{eq:db-case-3}
\ee

似应为：

\begin{array}{rcl}
\text{...} & & \\

fixB^2\ \mathcal{C}\ a_{\mathcal{B}^2}\ x\ (\mathcal{B}, b, y, c) & = & fixB^2\ shiftB\ (\mathcal{C}, (shiftB\ a), x, (\mathcal{R}, b, y, c)) \\

fixB^2\ \mathcal{C}\ (\mathcal{B}, a, x, b)\ y\ c_{\mathcal{B}^2} & = & fixB^2\ shiftB\ (\mathcal{C}, (\mathcal{R}, a, x, b), y, (shiftB\ c)) \\

fixB^2\ \mathcal{C}\ l\ k\ r\ & = & (\mathcal{C}, l, k, r) \\
\end{array}

第一行公式，因为$shiftB$可能生成双重黑色节点（除非知道原节点为红或双重黑，如式中右侧的$shiftB\ a$），所以外面应该套上$fixB^2$来消除这种双重黑色节点。

第二行公式的原文和图4.10的下部部分对不上。应该图的上部部分对称，即和第一行公式对称。

Just read your book, it's awesome, http://www.ituring.com.cn/book/1907, first Chinese book to introduce traditional data structures and algorithms with lots of functional languages code snippets.

I found some errata:

appendix

typo

I found a typo in Appendix, page 505. This line https://github.com/liuxinyu95/AlgoXY/blob/zh-cn/others/appendix/list/list-zh-cn.tex#L320 , in the published Chinese book, is not indent properly, which may results some confusions to the readers.

Maybe it should be recorded in a errata.

code listing error

In page 548

The code should be a plain code environment (aha, I know that it is a lstlisting environment in LaTeX), so it should not contains a \lambda character, and the \rightarrow should be plain -> as in Haskell code.

I've also checked the LaTeX source code here https://github.com/liuxinyu95/AlgoXY/blob/algoxy/others/appendix/list/list-en.tex#L3071 and here https://github.com/liuxinyu95/AlgoXY/blob/zh-cn/others/appendix/list/list-zh-cn.tex#L2651 and found these two line are correct. So I think this should be put into some errata list.

section title error

Page 549, the subsubsection title is not right, it should not start with a "4". It seems that this error has been fixed in https://github.com/liuxinyu95/AlgoXY/blob/zh-cn/others/appendix/list/list-zh-cn.tex#L2692 .

WORD_LENGTH 宏设置的有问题：没有括号
#define WORD_LENGTH (sizeof(int)*8)

Move list to the first chapter.
algoxy-zh-cn.pdf
algoxy-en.pdf

Hello @liuxinyu95 ,

Thanks for this wondefrul work. Can you please release latest version's PDF?

https://github.com/liuxinyu95/AlgoXY/blob/algoxy/datastruct/elementary/queue/queue-zh-cn.tex

-- 824 行
next (Concat 0 _ acc) = Done acc

在这里按照上文定义似乎应该是

next (Concat [] acc) = Done acc

3.3节“二分查找”末尾：

使用二分查找后，比较次数提高到了$O(n \lg n)$，但移动次数还是$O(n^2)$。

感觉这里“提高”不妥。是不是用“比较次数降低到了……”，或“比较性能提高到了……”合适些？

in CHAPTER 12.9.1
formula 12.34 提到 "... , gets the result O(n lg n)."

我整理T(n) 的遞迴式之後得到：
T(n) = 2T(n/2) + Θ( n log n )
這樣根據master theorem會得到：
T(n) = Θ( n(log n)^2 )
跟文中敘述不符。

During pdf generation, Latex complains that this label is defined two times
Here:

And here:

https://github.com/liuxinyu95/AlgoXY/releases

公式（4.1）中有：

rotate_l\ ((a, x, b), y, c) & = & (a, x, (b, y, c)) \

这里，rotate_l的参数怎么理解？

从直观上，我是理解为(a, x, b)是一棵x为父节点，a、b分别为左右子节点的子树。这样，((a, x, b), y, c)对应于图4.3“树的左右旋转”中的右侧，即在图中以y为根。而上式等号右侧对应的是图4.3的左侧，以x为根的子树。

可这样以来，公式（4.1）定义的操作就应该是右旋转吧，用rotate_r表示合适？下面的算法LEFT-ROTATE将图4.3中的左侧子树变换成了右侧子树。

还是我对(a, x, b)的理解有误？

如题，pdf有时候不在laptop上看不方便.提供个电子书格式平时看会方便很多 ，谢谢

第四章红黑树开头：

能否是用二叉搜索树处理通讯录，……

似应为 “能否使用二叉搜索树……”，或“是否能用二叉搜索树……”

书中是这样描述的：一个子节点为双重黑色空节点，另外一个子分支不为空，我们可以安全地将其变为普通的NIL。
这里直接删除的话，不是会使其它节点到这个NIL节点的路径中黑色节点数少一个，破坏任何红黑树的性质5了吗？

This is image holder for the cover page.