2016-12-16 81 views
1

我需要幫助理解一個特殊的鋸齒形和鋸齒形旋轉的例子。我已經在一本書,維基百科以及其他一些在線資源中閱讀了關於它們的內容,雖然當它們應用於簡單樹(即節點非常少的樹)時我可以理解它們,但是當我看到示例時我迷失了方向它們適用於更大的樹木(即具有更多節點的樹木)。Splay樹:鋸齒形和曲折形旋轉如何工作,具體如何?

特別是,我不理解這些實施例2的至少一個:

實施例1

Splay example 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次旋轉。

然後是該另一實施例: Splay example 2

在該例子中,噴射操作涉及鋸齒鋸齒。如你所見,只有一次旋轉。然後是第二次展開,因爲正在訪問的節點仍然不在根位置。

我會在這裏預期的是:

  • 任的鋸齒鋸齒和鋸齒提供的是正確的,因此就不會有第二個示例2轉的描述:一個繞節點的祖父母,然後是其父母。
  • 或者,所提供的描述是錯誤的,所以第二個例子是正確的,但第一個不是我們將它的父節點,而是它的祖父節點放在Z字形位置時旋轉了節點。

你能告訴我這兩個例子中的任何一個是錯的嗎?哪一個是錯的?如果他們都不對,我錯在哪裏?

謝謝你的幫助。

附:由於很明顯我是一名學生,我只想告訴你,我不會在任務中提出這個問題,因此我不會作弊。然而,我在星期一到來的時候會有一個考試,我希望在我參加考試之前有任何的誤解。

回答

0

張開一個節點X是張開的序列步驟直到X成爲樹的根。這些步驟是曲折,曲折和曲折。

對於節點X,其父pp的父Z字形節點操作X一個情況被定義,其中p是不根和Xpp的右子是左子:第一循環左移x,然後右轉x。你的第一個例子精確地顯示了這種情況:zig向左旋轉x =(8,X)及其父項 =(7,T),然後zag向右旋轉(8,X),並且= =一個)。因此,此示例顯示的曲折形狀爲x,但由於x尚未生成根(這意味着需要更多播放步驟),所以播放本身並未完成。

鋸齒鋸齒爲當兩個Xp是其各自父母的兒童的權利的情況下定義的:首先向左旋轉p,然後向左旋轉X。第二個例子的第二圖爲X =鋸齒鋸齒(40,X),p =(37,P), =(35,R)的結果:第一p是向左旋轉,然後向左旋轉x。第二示例的第三圖爲X(旋轉左X因爲其父p是根)移動到根和精加工的X張開附加鋸齒操作。 (所有的鋸齒,之字形和鋸齒形操作都有其對稱的對應物)。