關於伸展樹

Question

我讀到一本關於馬克·艾倫Wesis

的張開戰略，數據結構和算法伸展樹類似於旋轉的想法，但我們 是多了幾分挑剔的旋轉如何執行。我們將 仍然沿着訪問路徑自下而上旋轉。讓x是我們正在旋轉的訪問路徑上的（非根） 節點。如果x 的父項是樹的根，我們只需旋轉x和根。這是沿着訪問路徑的最後一個旋轉 。否則，x具有父項 （p）和祖父母（g），並且有兩種情況，加上對稱性 要考慮。第一種情況是曲折情況，這裏x是右邊的 孩子，p是左邊的孩子（反之亦然）。如果是這種情況，我們 執行雙轉，就像AVL雙轉。 否則，我們有一個之字形的情況：x和p要麼都是 子女，要麼都是正確的子女。

在上面的文字中作者所說的「有兩種情況加對稱性」是什麼意思？給出了兩種情況，但這裏的對稱性是什麼？

謝謝！

Answer 1

我認爲這只是非常基本的軸向symetry：

例如爲鋸齒形的情況下，這裏有2個對稱的樹：

 g 
    /\ 
    p d 
    /\ 
    c x 
    /\ 
    a b 

    g 
    /\ 
    d p 
     /\ 
    x c 
    /\ 
    a b 

Answer 2

例如，假設一個案例是「當問題節點是其父母的正確孩子，父母是祖父母的左邊孩子「在這種情況下，您需要左旋並右旋。所以節點會來到盛大的家長。

這種情況的對稱部分是「當問題中的節點是其父母的左邊孩子，而父母是祖父母的右邊孩子」。在這種情況下，您將執行右旋轉然後左旋。所以節點會來到盛大的家長。

用左右取代左右對稱的情況。

只有三種情況下在一個splay樹中旋轉。列出它here 你可以看到運行時在使用和不使用splaying時的差異。