[理工] 紅黑樹DS版本/演算法版本問題

[jwlhs104 (機智小字典)]

資料結構筆記有提到說紅黑樹分為DS版本和演算法版本
DS版本是由2-3-4 tree轉換而來
而演算法的版本是直接定義紅黑樹的規則
我遇到的題目是在紅黑樹中insert順序的不同是否會改變紅色Node的數量
然後我試著以DS版本找例子


先以123456的順序建立一個2-3-4 tree
https://i.imgur.com/IqQDP6E.png
轉換過後得到的red-black tree有2個紅色的Node


再以654321的順序建立一個2-3-4 tree
https://i.imgur.com/cQVswUg.png
轉換過後得到的red-black tree有3個紅色的Node

因此DS版本中答案應該是有可能會改變的


但同樣的例子用演算法版本卻不是這樣

以123456順序建立的red-black tree
https://i.imgur.com/uRqQ7wt.png

以654321順序建立的red-black tree
https://i.imgur.com/IeTCESO.png

兩個樹皆有2個紅色的Node



所以現在我的疑惑是
1. DS版本和演算法版本建立出來的紅黑樹會不一樣嗎?
2. 題目本身：紅黑樹中insert順序不同是否會改變紅色Node的數量?

還請各位大神幫幫忙
感謝感謝

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.112.245.51
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1543772086.A.F3C.html
推 FRAXIS: 兩個答案都 YES