2022-5-22
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 树的最大数字和就会减小。
...
2022-6-25
3.3.14 # 解答 # 官网有解答：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 树最右侧叶子结点的右侧插入元素，对应红黑树的高度是单调递增的，具体说明见上一题的解答。
A ||-B A |-B-| A C |---B---| A ||-D C ||---D---| |-B-| E A C ||---D---| |-B-| ||-F A C E |---D---| |-B-| |-F-| A C E G |-------D-------| |---B---| |---F---| A C E ||-H G |-------D-------| |---B---| ||---H---| A C |-F-| I E G |-------D-------| |---B---| ||---H---| A C |-F-| ||-J E G I ||-------H-------| |---D---| |---J---| |-B-| |-F-| I K A C E G
2022-6-30
3.3.15 # 解答 # 官网有解答：https://algs4.cs.princeton.edu/33balanced/
红黑树的构造过程，|| 代表红链接。
递减顺序插入等价于一直向 2-3 树最左侧叶子结点的左侧插入元素，对应红黑树的高度不一定是单调递增的（本例中插入 E 的时候红黑树高度反而减小了），具体说明见 3.3.13 的解答。
K ||-K J |-J-| I K |---J---| ||-I K H ||---J---| |-H-| K G I ||-------J-------| |---H---| K ||-G I F |---H---| |-F-| |-J-| E G I K |-------H-------| |---F---| |---J---| ||-E G I K D |-------H-------| ||---F---| |---J---| |-D-| G I K C E |---------------H---------------| ||-------F-------| |-------J-------| |---D---| G I K ||-C E B ||-------H-------| |---D---| |---J---| |-B-| |-F-| I K A C E G
2022-11-8
3.3.16 # 解答 # 这棵红黑树看起来就像这样（||代表红链接）。
||---------------------------------------------------------------t---------------------------------------------------------------| j-------------------------------| u |---------------r---------------| |-------p-------| s |---l---| q k |-n-| m o
2023-2-25
3.3.17 # 解答 # 创建一个数组并随机打乱即可，下面是两个例子：
G,A,E,K,H,D,F,L,C,O,I,B,M,P,J,N |-------------------------------G-------------------------------| A---------------| |---------------K---------------| |-------E-------| H-------| L-------| |---D F I---| |---O---| |-C J M-| P B N ||-------------------------------L-------------------------------| |---------------E---------------| |---------------O---------------| |-------C-------| ||-------J-------| ||-------N P ||---B D |---H---| K M A ||-G I F 第二个例子：
A,N,C,J,F,O,B,M,P,L,K,D,E,H,G,I A---------------------------------------------------------------| |-------------------------------N-------------------------------| |---------------C---------------| O---------------| B |-------J-------| P |---F---| |---M D-| |-H-| |-L E G I K ||---------------J---------------| |-------E-------| ||-------N-------| |---C---| |---G---| |---L---| ||---P ||-B D F ||-I K M O A H 代码 # using BalancedSearchTree; var keys = Enumerable.
...