[理工] 紅黑樹DS版本/演算法版本問題
資料結構筆記有提到說紅黑樹分為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
推
12/03 06:18,
7年前
, 1F
12/03 06:18, 1F