splay-tree

1熱度

1回答

我在一個數據結構是當然，現在我們瞭解了2-3-4樹和伸展樹。我想知道在什麼情況下你會使用2-3-4的樹而不是張大的樹？他們都是自我平衡和排序，所以我沒有看到他們之間的差異。

0熱度

1回答

我想在java中做一個自下而上的張大樹。但不知何故，當我構建一棵樹，添加幾個元素，並嘗試將插入的節點展開到頂部時，我會在我的旋轉方法中得到一個空指針異常。誰能告訴我爲什麼我會得到這個錯誤？基本上，我有一個左指針，右指針，父指針，根節點和splayNode持有者這個泛型SPTNode類。它還具有單旋轉，ZigZig旋轉，ZigZag旋轉，展曲和插入方法的方法。這裏是我的比較級： import j

4熱度

3回答

Splay樹插入

通過一些練習來磨練我的二叉樹技能，我決定實現一個splay樹，如Wikipedia: Splay tree中所述。我沒有得到的一件事是關於插入的部分。它說：首先，我們在伸展樹搜索X。如果x不存在，那麼我們不會找到它，但它的父節點y。其次，我們對y執行splay操作，這會將y移動到splay樹的根部。第三，我們以適當的方式以root身份插入新的節點x。以這種方式，y是新的根x的左邊或右邊的孩子

5熱度

2回答

std :: map允許在只讀操作（如Splay樹）之後重新平衡

某些二叉樹數據結構（如Splay樹）將在讀取時重新平衡以將最近訪問的項目移動到根目錄，使得隨後的查找時間可以減少。標準容器（std::map,std::set）是否允許這樣做？至少有一個問題是線程安全。以前，我認爲只要你只對標準容器進行只讀操作，從多線程做到這一點是安全的，而不會引入互斥/鎖等。也許我需要重新考慮這一點？我知道通常是紅黑樹用於標準樹容器，並且這些數據結構通常不會在讀取時被修改

3熱度

2回答

遞歸Splay樹

我想實現一個遞歸的splay樹，自下而上。我遞歸到我需要展開的節點，並找到該節點的父節點和祖父節點。然後，我可以根據情況做出曲折或曲折的曲折。問題是在完成之後，我將返回已經展開一次的節點返回到先前的遞歸調用。先前的遞歸調用被引用到該節點的父節點，該節點現在是該節點的子節點。隨着我上升，我該如何遞增節點？

0熱度

1回答

測試Splay樹

我正在嘗試在網上找到一個applet來測試splay樹，但是目前爲止我沒有發現它們滿足我需要的東西。我需要一些可以輸入已經構建的splay樹的東西。我有最初的樹，但不能使用插入來構造它，因爲我不知道它的順序。理想情況下，我正在尋找一個拖放小程序。

0熱度

2回答

關於伸展樹

我讀到一本關於馬克·艾倫Wesis 的張開戰略，數據結構和算法伸展樹類似於旋轉的想法，但我們是多了幾分挑剔的旋轉如何執行。我們將仍然沿着訪問路徑自下而上旋轉。讓x是我們正在旋轉的訪問路徑上的（非根）節點。如果x 的父項是樹的根，我們只需旋轉x和根。這是沿着訪問路徑的最後一個旋轉。否則，x具有父項（p）和祖父母（g），並且有兩種情況，加上對稱性要考慮。第一種情況是曲折情況，這裏x是右邊的

6熱度

1回答

展開樹的攤銷成本：費用+ P（tf）-P（ti）≤3（rankf（x） - ranki（x））解釋

在閱讀有關展曲樹時，我發現了一些表達式， 'X'和維基百科中的攤銷成本。它被給定爲， { 我們可以通過結合的任何鋸齒鋸齒或鋸齒形操作的攤銷成本： amortized cost = cost + P(tf) - P(ti) ≤ 3(rankf(x) - ranki(x)), ，其中X是節點被移動朝向根，下標「F」和「i」分別表示手術之後和手術前。當對整個展放操作求和時，這個望遠鏡到3（等級（根）

31熱度

2回答

AVL樹和斜紋樹的區別

我正在研究各種樹木，並且遇到了AVL樹和斜紋樹。我想知道 AVL樹和斜張樹有什麼區別？我們選擇這些樹的基礎是什麼？這些樹的積極和消極的是什麼？這些樹在大O符號方面表現如何？