JS如何实现Splay树？伸展树的旋转-js教程-PHP中文网

伸展树的旋转操作分为Zig（单旋）、Zig-Zig（同向双旋）和Zig-Zag（异向双旋），在插入、查找或删除后执行_splay时根据节点与父、祖父节点的相对位置触发。Zig用于节点父节点为根的情况，Zig-Zig用于三代同侧，Zig-Zag用于三代折线结构，通过组合旋转高效压缩路径，提升后续访问性能。

js如何实现splay树？伸展树的旋转

JS实现伸展树（Splay Tree），核心在于理解其独特的“伸展”操作，而这个操作又完全依赖于几种精心设计的树旋转。简单来说，伸展树是一种自平衡二叉搜索树，它通过将最近访问的节点移动到树的根部来优化后续访问的效率。在JavaScript中实现它，你需要构建一个包含父指针的节点结构，并实现左右旋转，然后将这些旋转组合成复杂的伸展逻辑。

解决方案

实现伸展树在JavaScript中，首先需要定义一个节点类，它不仅包含键值和左右子节点，更关键的是要包含一个指向父节点的引用。这是伸展操作能够“向上”遍历的关键。

class SplayTreeNode {
    constructor(key, value = null) {
        this.key = key;
        this.value = value;
        this.left = null;
        this.right = null;
        this.parent = null; // 伸展树的关键：父指针
    }
}

class SplayTree {
    constructor() {
        this.root = null;
    }

    // 辅助方法：右旋
    // 假设 node 是要被旋转的子树的根（它将成为新根的右子节点）
    _rotateRight(node) {
        const parent = node.parent;
        const leftChild = node.left;

        // 执行旋转
        node.left = leftChild.right;
        if (leftChild.right) {
            leftChild.right.parent = node;
        }
        leftChild.right = node;
        node.parent = leftChild;

        // 更新父节点的引用
        if (parent) {
            if (parent.left === node) {
                parent.left = leftChild;
            } else {
                parent.right = leftChild;
            }
        } else {
            this.root = leftChild; // 更新树的根
        }
        leftChild.parent = parent;
    }

    // 辅助方法：左旋
    // 假设 node 是要被旋转的子树的根（它将成为新根的左子节点）
    _rotateLeft(node) {
        const parent = node.parent;
        const rightChild = node.right;

        // 执行旋转
        node.right = rightChild.left;
        if (rightChild.left) {
            rightChild.left.parent = node;
        }
        rightChild.left = node;
        node.parent = rightChild;

        // 更新父节点的引用
        if (parent) {
            if (parent.right === node) {
                parent.right = rightChild;
            } else {
                parent.left = rightChild;
            }
        } else {
            this.root = rightChild; // 更新树的根
        }
        rightChild.parent = parent;
    }

    // 核心操作：伸展（Splay）
    // 将指定节点 x 伸展到树的根部
    _splay(x) {
        while (x.parent) {
            const p = x.parent; // 父节点
            const g = p.parent; // 祖父节点

            if (!g) { // Zig case: x is a child of the root
                if (p.left === x) { // x is left child of p
                    this._rotateRight(p);
                } else { // x is right child of p
                    this._rotateLeft(p);
                }
            } else { // Zig-Zig or Zig-Zag case
                if (p.left === x && g.left === p) { // Zig-Zig (left-left)
                    this._rotateRight(g);
                    this._rotateRight(p);
                } else if (p.right === x && g.right === p) { // Zig-Zig (right-right)
                    this._rotateLeft(g);
                    this._rotateLeft(p);
                } else if (p.left === x && g.right === p) { // Zig-Zag (right-left)
                    this._rotateRight(p);
                    this._rotateLeft(g);
                } else { // Zig-Zag (left-right)
                    this._rotateLeft(p);
                    this._rotateRight(g);
                }
            }
        }
        this.root = x; // x 现在是新的根
    }

    // 插入操作
    insert(key, value = null) {
        if (!this.root) {
            this.root = new SplayTreeNode(key, value);
            return;
        }

        let current = this.root;
        let parent = null;
        let newNode = null;

        while (current) {
            parent = current;
            if (key < current.key) {
                current = current.left;
            } else if (key > current.key) {
                current = current.right;
            } else {
                // 键已存在，更新值并伸展
                current.value = value;
                this._splay(current);
                return;
            }
        }

        newNode = new SplayTreeNode(key, value);
        newNode.parent = parent;

        if (key < parent.key) {
            parent.left = newNode;
        } else {
            parent.right = newNode;
        }

        this._splay(newNode); // 插入后伸展新节点
    }

    // 查找操作
    find(key) {
        let current = this.root;
        let lastVisited = null; // 记录最后访问的节点，即使没找到也伸展它

        while (current) {
            lastVisited = current;
            if (key < current.key) {
                current = current.left;
            } else if (key > current.key) {
                current = current.right;
            } else {
                this._splay(current); // 找到后伸展
                return current.value;
            }
        }

        // 没找到，但仍然伸展最后访问的节点
        if (lastVisited) {
            this._splay(lastVisited);
        }
        return undefined; // 未找到
    }

    // 删除操作
    delete(key) {
        this.find(key); // 首先将要删除的节点伸展到根

        if (!this.root || this.root.key !== key) {
            // 节点不存在或伸展后根不是要删除的节点
            return false;
        }

        const nodeToDelete = this.root;
        let leftSubtree = nodeToDelete.left;
        let rightSubtree = nodeToDelete.right;

        // 断开与根的连接
        if (leftSubtree) {
            leftSubtree.parent = null;
        }
        if (rightSubtree) {
            rightSubtree.parent = null;
        }

        if (!leftSubtree) {
            this.root = rightSubtree; // 左子树为空，右子树直接成为新根
        } else {
            // 将左子树的最大节点伸展到左子树的根
            let maxNodeInLeft = leftSubtree;
            while (maxNodeInLeft.right) {
                maxNodeInLeft = maxNodeInLeft.right;
            }
            // 伸展操作会自动将maxNodeInLeft提升到leftSubtree的根
            this._splay(maxNodeInLeft); 
            // 此时maxNodeInLeft已经是leftSubtree的根，且没有右子节点
            // 将原右子树连接到新的根（maxNodeInLeft）的右侧
            maxNodeInLeft.right = rightSubtree;
            if (rightSubtree) {
                rightSubtree.parent = maxNodeInLeft;
            }
            this.root = maxNodeInLeft; // 更新整个树的根
        }
        return true;
    }

    // 遍历（可选，用于验证）
    inOrderTraversal(node = this.root, result = []) {
        if (node) {
            this.inOrderTraversal(node.left, result);
            result.push(node.key);
            this.inOrderTraversal(node.right, result);
        }
        return result;
    }
}

登录后复制

伸展树的旋转操作有哪些类型，它们在何时被触发？

伸展树的旋转操作主要分为三种基本类型：Zig (单旋)、Zig-Zig (同向双旋) 和 Zig-Zag (异向双旋)。它们的核心目的都是为了在“伸展”一个节点时，高效地将其向上移动到树的根部，并在此过程中尽可能地平衡树的结构。

Zig (单旋)：当目标节点
```
x
```
登录后复制
是其父节点
```
p
```
登录后复制
的直接子节点，且
```
p
```
登录后复制
本身就是树的根时，就会触发Zig操作。这本质上就是一次标准的二叉搜索树旋转（左旋或右旋），将
```
x
```
登录后复制
提升为新的根。例如，如果
```
x
```
登录后复制
是
```
p
```
登录后复制
的左孩子，则进行右旋；如果
```
x
```
登录后复制
是
```
p
```
登录后复制
的右孩子，则进行左旋。这是伸展操作的最后一步，或者当目标节点恰好在根的下一层时发生。
Zig-Zig (同向双旋)：当目标节点
```
x
```
登录后复制
、其父节点
```
p
```
登录后复制
和祖父节点
```
g
```
登录后复制
都位于一条直线上时（例如，
```
x
```
登录后复制
是
```
p
```
登录后复制
的左孩子，
```
p
```
登录后复制
又是
```
g
```
登录后复制
的左孩子，形成一个“左-左”链），就会触发Zig-Zig操作。这种情况下，会连续执行两次相同方向的旋转。具体来说，会先对
```
g
```
登录后复制
进行一次旋转（将
```
p
```
登录后复制
提升），然后对新的根（原
```
p
```
登录后复制
）进行一次旋转（将
```
x
```
登录后复制
提升）。值得注意的是，这两次旋转的顺序很重要，是先对祖父节点旋转，再对父节点旋转。这种组合旋转能更有效地减少
```
x
```
登录后复制
到根的路径长度。
Zig-Zag (异向双旋)：当目标节点
```
x
```
登录后复制
、其父节点
```
p
```
登录后复制
和祖父节点
```
g
```
登录后复制
形成一个“折线”时（例如，
```
x
```
登录后复制
是
```
p
```
登录后复制
的左孩子，但
```
p
```
登录后复制
却是
```
g
```
登录后复制
的右孩子，形成一个“右-左”折线），就会触发Zig-Zag操作。这种情况下，会执行两次不同方向的旋转。先对
```
p
```
登录后复制
进行一次旋转（将
```
x
```
登录后复制
提升到
```
p
```
登录后复制
的位置），然后对
```
g
```
登录后复制
进行一次旋转（将
```
x
```
登录后复制
提升到
```
g
```
登录后复制
的位置）。这两次旋转可以看作是独立的，但它们共同作用，将
```
x
```
登录后复制
直接提升到
```
g
```
登录后复制
的位置，并进一步向根移动。

这些旋转操作并非独立触发，它们都是在

_splay(x)

登录后复制

这个核心方法内部，根据

登录后复制

、

x.parent

登录后复制

和

x.parent.parent

登录后复制

的相对位置动态选择和执行的。每当对伸展树执行一次

insert

登录后复制

（插入）、

find

登录后复制

（查找）或

delete

登录后复制

（删除）操作时，都会调用

_splay

登录后复制

方法，将相关节点（新插入的节点、找到的节点或删除操作中涉及的辅助节点）移动到树的根部。这个过程就是这些旋转被触发的时机。

为什么伸展树选择这些特定的旋转策略，而不是简单的单旋转？

伸展树之所以采用Zig-Zig和Zig-Zag这种复杂的组合旋转，而非仅仅是简单的单次旋转（比如像AVL树那样每次只做一次单旋或双旋来局部平衡），其核心原因在于摊还分析（Amortized Analysis）下的性能优化。

如果伸展树仅仅使用简单的单旋转来将节点向上移动，例如，对于一个Zig-Zig的场景，如果只是简单地执行两次Zig操作（先将

登录后复制

旋转到

登录后复制

的位置，再将

登录后复制

旋转到

登录后复制

的位置），那么在最坏情况下，树的深度可能仍然不会得到有效压缩。想象一下，如果树是一个长长的“链条”，每次访问链条末端的节点，如果只进行单旋，那么每次旋转都只是将节点向上移动了一层，而链条的整体结构并没有被显著改变。这会导致后续对链条上其他节点的访问仍然需要遍历很长的路径，从而使得操作的摊还时间复杂度可能退化到O(N)。

Zig-Zig和Zig-Zag的设计，是为了更激进地“压缩”路径。它们的目的不仅仅是将目标节点移动到根部，更重要的是在移动过程中，尽可能地将路径上的其他节点也向上提升，从而将路径的深度大致减半。

Zig-Zig：它通过两次同向旋转，能够将目标节点
```
x
```
登录后复制
直接提升到其祖父节点
```
g
```
登录后复制
的位置，并且在旋转过程中，将
```
p
```
登录后复制
和
```
g
```
登录后复制
也向上提升，使得
```
x
```
登录后复制
到根的路径上，每一步都减少了两层。这就像是“跳跃式”的提升，比两次独立的单旋效果更好，它能更好地“摊平”树的高度。
Zig-Zag：虽然看起来也是两次旋转，但其效果是让目标节点
```
x
```
登录后复制
直接取代其祖父节点
```
g
```
登录后复制
的位置。这种“V”字形结构的转换，同样能有效地缩短
```
x
```
登录后复制
到根的路径，并且其局部平衡效果也比两次单旋叠加要好。它避免了单旋可能导致的某些子树失衡问题。

Boomy
AI音乐生成工具，创建生成音乐,与世界分享.

272

查看详情

通过这些特定的组合旋转，伸展树保证了对任意一系列M次操作（查找、插入、删除），其总的时间复杂度为O(M log N)，这意味着每次操作的摊还时间复杂度是O(log N)。这种摊还性能是伸展树的主要优势，它在不维护严格平衡条件（如AVL树的高度平衡因子或红黑树的颜色规则）的情况下，依然能提供良好的平均性能。它牺牲了最坏情况下的单次操作性能（单次操作可能仍然是O(N)），换取了序列操作的整体高效性。

在JavaScript中实现伸展树时，有哪些常见的陷阱或需要注意的细节？

在JavaScript中实现伸展树，虽然概念上清晰，但实际编码时确实有一些细节非常容易出错，导致程序行为异常或性能不达预期。

父指针的正确维护： 这是伸展树实现中最最关键也最容易出错的地方。每次进行旋转操作时，不仅要调整左右子节点的关系，更重要的是要精确地更新所有受影响节点的
```
parent
```
登录后复制
指针。一个父指针的错误，可能导致整个树的结构混乱，后续的伸展操作将无法正确地向上遍历，甚至陷入死循环。例如，当一个节点成为新根时，它的
```
parent
```
登录后复制
应该设为
```
null
```
登录后复制
；当一个节点被旋转到某个位置时，它的新父节点必须正确指向它，反之亦然。务必对每个旋转操作的每一步都仔细检查父指针的更新逻辑。
根节点的更新： 当旋转操作将原先的根节点移走，或者伸展操作将一个非根节点提升为新根时，必须及时更新
```
this.root
```
登录后复制
属性。如果忘记更新，树的入口点就会失效，后续的所有操作都将基于错误的根节点进行。
空值（null）检查： 在进行旋转操作或遍历树时，需要频繁地访问
```
node.left
```
登录后复制
、
```
node.right
```
登录后复制
、
```
node.parent
```
登录后复制
等属性。在访问这些属性之前，总是要进行空值检查，以防止对
```
null
```
登录后复制
引用进行属性访问导致运行时错误。比如，
```
node.left.right
```
登录后复制
之前，要确保
```
node.left
```
登录后复制
不为
```
null
```
登录后复制
。
伸展操作的边界条件：
```
_splay
```
登录后复制
函数的循环条件是
```
while (x.parent)
```
登录后复制
。这意味着当
```
x
```
登录后复制
成为根节点时，循环就会终止。但需要确保在循环内部的
```
Zig
```
登录后复制
、
```
Zig-Zig
```
登录后复制
、
```
Zig-Zag
```
登录后复制
判断逻辑中，对
```
g
```
登录后复制
(祖父节点) 的存在性判断是正确的。
```
if (!g)
```
登录后复制
对应Zig情况，而
```
else
```
登录后复制
块则处理有祖父节点的情况。
删除操作的复杂性： 伸展树的删除操作比插入和查找要复杂得多。它通常分两步：
1. 将要删除的节点伸展到根。
2. 将该根节点删除后，其左右子树需要重新合并。常见的做法是，将左子树的最大节点（或右子树的最小节点）伸展到左子树的根，然后将原右子树连接到这个新根的右侧。这个过程需要非常小心地处理父指针和根节点的更新。
调试的挑战： 伸展树的动态特性使得其调试变得困难。树的结构在每次操作后都会发生显著变化，单步调试往往难以追踪整个结构的变化。我个人建议，在调试时，可以尝试打印出每次旋转或伸展后树的结构（例如，使用简单的层序遍历打印节点及其父子关系），或者使用可视化工具来帮助理解。
JavaScript的引用特性： JavaScript中对象是按引用传递的。这意味着当你将一个节点赋值给另一个变量时，它们指向的是同一个对象。在修改节点属性时，要清楚这种引用关系，确保修改的是正确的对象实例，并且所有相关的引用都得到了恰当的更新。