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