我需要幫助理解一個特殊的鋸齒形和鋸齒形旋轉的例子。我已經在一本書,維基百科以及其他一些在線資源中閱讀了關於它們的內容,雖然當它們應用於簡單樹(即節點非常少的樹)時我可以理解它們,但是當我看到示例時我迷失了方向它們適用於更大的樹木(即具有更多節點的樹木)。Splay樹:鋸齒形和曲折形旋轉如何工作,具體如何?
特別是,我不理解這些實施例2的至少一個:
實施例1
我們可以看到(1)這是即將被張開的節點是左子右孩子,所以我們要做的曲折。因此,我可以理解(1)和(2)之間發生了什麼,其中展開的節點現在取代了它的父節點。據我瞭解,整個之字形操作發生在那裏。所以第一個展示結束了,我們仍然需要展開節點,直到它位於樹的根部。 (2)和(3)之間發生了什麼。我不明白(2)和(3)之間會發生什麼。在(2)中,展開的節點是左孩子的左孩子,所以我期望Z字形操作,由此被展開的節點圍繞其祖父母旋轉,即(20,Z)。相反,幻燈片會顯示其父項(10,A)的旋轉。爲什麼?我所期望的是,我們的splaying節點(8,N)做了一個之字形,從而取得了作爲其祖父母的(20,N)以及根的地方。爲什麼涉及父母?
在我發現這個例子(我的講師的幻燈片),鋸齒形旋轉被描述爲資源「其父母旋轉點,然後旋轉以其宏大的父母節點」。這是發生在這裏嗎?這是(2)和(3),(8,N)之間爲什麼會以(10,A)而不是(20,Z)旋轉的原因?
我對這個描述非常困惑,因爲這時鋸齒鋸齒旋轉被描述爲「以其宏大的父母旋轉節點,然後旋轉節點與其父」。然而,每當我看到一個Z字形旋轉的例子時,總是隻有一個旋轉與該節點的祖父母,就是這樣。我從來沒有見過2次旋轉。
在該例子中,噴射操作涉及鋸齒鋸齒。如你所見,只有一次旋轉。然後是第二次展開,因爲正在訪問的節點仍然不在根位置。
我會在這裏預期的是:
- 任的鋸齒鋸齒和鋸齒提供的是正確的,因此就不會有第二個示例2轉的描述:一個繞節點的祖父母,然後是其父母。
- 或者,所提供的描述是錯誤的,所以第二個例子是正確的,但第一個不是我們將它的父節點,而是它的祖父節點放在Z字形位置時旋轉了節點。
你能告訴我這兩個例子中的任何一個是錯的嗎?哪一個是錯的?如果他們都不對,我錯在哪裏?
謝謝你的幫助。
附:由於很明顯我是一名學生,我只想告訴你,我不會在任務中提出這個問題,因此我不會作弊。然而,我在星期一到來的時候會有一個考試,我希望在我參加考試之前有任何的誤解。