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