SplayTree詳解

一、SplayTree簡介

SplayTree是一種自平衡的二叉搜索樹，既能支持查找、插入、刪除操作，又可以在O(logn)的平均時間複雜度下完成。它採用了一種叫做伸展的操作，通過將最近訪問的節點旋轉到根節點，來優化樹的形態，從而使下一次查找更加高效。

SplayTree的特點在於它的平均維護代價非常低，而不像其他平衡樹結構，如AVL樹或紅黑樹那樣，需要在每次插入或刪除時進行大量的旋轉操作。因此，在實際應用中，SplayTree被廣泛使用。

二、SplayTree的操作

1、旋轉操作

// 以x節點為根的子樹向右旋轉
private Node rightRotate(Node x) {
    Node y = x.left;
    x.left = y.right;
    y.right = x;
    return y;
}

// 以x節點為根的子樹向左旋轉
private Node leftRotate(Node x) {
    Node y = x.right;
    x.right = y.left;
    y.left = x;
    return y;
}

SplayTree的旋轉操作用來調整樹的形態，旋轉之後節點之間的大小關係仍然保持不變。

2、伸展操作

private Node splay(Node root, int key) {
    if (root == null || root.key == key) {
        return root;
    }
    if (root.key > key) {
        if (root.left == null) {
            return root;
        }
        // zig-zig
        if (root.left.key > key) {
            root.left.left = splay(root.left.left, key);
            root = rightRotate(root);
        // zig-zag
        } else if (root.left.key  key) {
            root.right.left = splay(root.right.left, key);
            if (root.right.left != null) {
                root.right = rightRotate(root.right);
            }
        // zag-zag
        } else if (root.right.key < key) {
            root.right.right = splay(root.right.right, key);
            root = leftRotate(root);
        }
        return root.right == null ? root : leftRotate(root);
    }
}

伸展操作是SplayTree的核心操作，它通過旋轉將所要查詢的節點旋轉到根節點，從而達到優化樹的目的，提高查詢效率。具體包含以下四種情況：

zig-zig：向右旋轉兩次
zag-zig：向左旋轉一次，向右旋轉一次
zig-zag：向右旋轉一次，向左旋轉一次
zag-zag：向左旋轉兩次

3、查找節點

public Node search(int key) {
    root = splay(root, key);
    return root.key == key ? root : null;
}

查找節點操作調用伸展操作，將所要查找的節點旋轉到根節點，並返回該節點。

4、插入節點

public void insert(int key, int value) {
    if (root == null) {
        root = new Node(key, value);
        return;
    }
    // 調用伸展操作將是否已存在該節點的判斷移動到了根節點
    root = splay(root, key);
    if (root.key == key) {
        root.value = value;
        return;
    }
    Node node = new Node(key, value);
    if (root.key > key) {
        node.right = root;
        node.left = root.left;
        root.left = null;
    } else {
        node.left = root;
        node.right = root.right;
        root.right = null;
    }
    root = node;
}

插入節點操作也通過伸展操作將被插入節點旋轉到根節點，之後判斷是否存在該節點，若存在則更新值；若不存在，則創建新節點並插入到根節點所在的位置。

5、刪除節點

public void delete(int key) {
    if (root == null) {
        return;
    }
    // 調用伸展操作將是否已存在該節點的判斷移動到了根節點
    root = splay(root, key);
    if (root.key != key) {
        return;
    }
    Node left = root.left, right = root.right;
    root = null;
    if (left != null) {
        left = splay(left, key);
        left.right = right;
        root = left;
    } else {
        root = right;
    }
}

刪除節點操作同樣通過伸展操作將被刪除節點旋轉到根節點，之後將左子樹的最大值（若存在）或右子樹的最小值（若左子樹為空）旋轉到根節點，再將其從樹中刪除。

三、SplayTree Map

1、SplayTree Map簡介

SplayTree Map是基於SplayTree實現的一種Map數據結構，它繼承了SplayTree的所有優點，並且實現了Map的所有介面，即支持鍵值對的查找、插入、刪除等常用操作。

2、SplayTree Map的代碼示例

插入節點

SplayTreeMap treeMap = new SplayTreeMap();
treeMap.put(1, "one");
treeMap.put(2, "two");
treeMap.put(3, "three");

刪除節點

SplayTreeMap treeMap = new SplayTreeMap();
treeMap.put(1, "one");
treeMap.put(2, "two");
treeMap.put(3, "three");
treeMap.remove(2);

查找節點

SplayTreeMap treeMap = new SplayTreeMap();
treeMap.put(1, "one");
treeMap.put(2, "two");
treeMap.put(3, "three");
treeMap.get(2);

四、SplayTree的應用

1、內存分配

SplayTree有一種叫做動態管理內存的應用，即SplayTree可以用來管理內存分配，通過不斷調整樹的形態來使得內存利用率更高。在這個場景下，每個節點表示一塊內存，節點的大小可以代表內存塊的大小，每次分配內存時，將根節點分裂成兩個子樹。分裂後，新分配的內存塊被插入到左子樹的最右端，原內存塊則成為右子樹的最左端。這樣，在分配內存時，可以從左往右遍歷樹來查找空閑的內存塊。

2、緩存淘汰策略

SplayTree在Web緩存、資料庫緩存等中可以用來實現淘汰策略。對於高並發場景，將SplayTree作為緩存管理的容器，在訪問緩存節點時調用伸展操作，將最近訪問的節點旋轉到根節點，從而保證經常被訪問的節點更容易被找到，降低查找成本。

3、文件壓縮

SplayTree在壓縮演算法中也有應用。具體來說，SplayTree可以用來實現Huffman壓縮演算法中的字典表，對於每個字元建立一個葉子節點，進行頻率統計後，使用伸展操作將頻率最小的節點移到根節點，以此來構建Huffman樹，從而壓縮數據。

結語

SplayTree是一種優秀的數據結構，不僅實現了平衡樹的功能，而且在日常編程中的應用場景非常廣泛。熟練掌握它的基本操作並靈活運用，能夠大大提高程序的效率。

原創文章，作者：小藍，如若轉載，請註明出處：https://www.506064.com/zh-tw/n/200290.html