最大。將新元素插入n元素紅黑樹時的旋轉次數

Question

將新元素插入n元素時的最大旋轉次數是多少？元素紅黑樹？

如果我是正確的，插入不違反RBT requries規則最大2旋轉（2例）。假設是這樣，O(1)也是一個正確的答案？

如果是這樣，確認它請告訴我，什麼需要最多3輪？

Answer 1

正確實施紅黑樹時，最多需要3次操作（或2次旋轉）。例如，此圖中顯示的中央BST將需要3次操作才能確認紅色黑色BST的規則。

_{圖片由羅伯特·塞奇威克的幻燈片從this MOOC拍攝。}。