3.3.13 #
解答 #
官网有解答：https://algs4.cs.princeton.edu/33balanced/#:~:text=True%20or%20false%3A%20If%20you%20insert%20keys%20in%20increasing%20order%20into%20a%20red%2Dblack%20BST%2C%20the%20tree%20height%20is%20monotonically%20increasing
是真的。
现在考虑在哪些情况下，红黑树插入元素后高度会变小。
根据红黑树与 2-3 树的对应，红链接其实就是把 2-3 树的 3-结点中的左侧元素变为左子树，并把这个左链接标记为红色。
那么对于一棵 2-3 树，3-结点对应的到红黑树中是带左侧结点的子树，高度会比同位置的 2-结点多 1。
现在把 2-3 树中的 2-结点记为 1，3-结点记为 2，数字最大的路径即为决定对应红黑树高度的路径。
那么只要插入操作后，该路径上的数字和反而减小，对应红黑树的高度不可能变大，只有可能减小或不变。（不变的原因和红黑树的性质有关，见之后的说明）
现在考虑 2-3 树插入的情况。
插入到 2-结点 -> 变为 3-结点，最大数字和增加。
插入到 3-结点 -> 自身变为 2-结点，向上传递 1 个元素
显然插入到 2-结点不可能减小高度，我们来考虑 3-结点向上传递的情况。
父结点是 2-结点 -> 父结点变为 3-结点，总数字和不变，红黑树高度不变。
父结点是 3-结点 -> 父结点变为 2-结点，向上传递一个元素。
不难发现当路径上有连续两个 3-结点时，插入操作最后会有两种情况：
- 停止在父级的某一个 2-结点。这时两个 3-结点变成了 2-结点（-2），一个 2-结点变成了 3-结点（+1），数字和减少 1
- 整棵 2-3 树的高度增加。这时两个 3-结点变成了 2-结点（-2），整条路径多了 1 个 2-结点（+1），数字和减少 1。
因此只有当该路径上最后两个元素都是 3-结点时，插入后的数字和必然减少，如果没有其他路径上的数字和比它更大，整个 2-3 树的最大数字和就会减小。
现在我们需要考虑定义的红黑树性质，只有 左链接 是红链接。
因此如果往一个 3-结点的右侧插入，对应红黑树的高度是不会变化的，只是左侧红链接变为黑色。
本题中元素是递增插入的，也就是一直向 2-3 树最右侧叶子结点的右侧插入，因此对应红黑树高度只会增加或不变。因此这种情况下红黑树高度是单调递增的。