JS如何实现Splay树？伸展树的旋转

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

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.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.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

、

x.parent

和

x.parent.parent

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

insert

（插入）、

find

（查找）或

delete

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

_splay

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

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

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

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

p

旋转到

g

的位置，再将

x

旋转到

p

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

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

Zig-Zig：它通过两次同向旋转，能够将目标节点

x

直接提升到其祖父节点

g

的位置，并且在旋转过程中，将

p

和

g

也向上提升，使得

x

到根的路径上，每一步都减少了两层。这就像是“跳跃式”的提升，比两次独立的单旋效果更好，它能更好地“摊平”树的高度。

Zig-Zag：虽然看起来也是两次旋转，但其效果是让目标节点

x

直接取代其祖父节点

g

的位置。这种“V”字形结构的转换，同样能有效地缩短

x

到根的路径，并且其局部平衡效果也比两次单旋叠加要好。它避免了单旋可能导致的某些子树失衡问题。

ViiTor实时翻译

AI实时多语言翻译专家！强大的语音识别、AR翻译功能。

116 查看详情

通过这些特定的组合旋转，伸展树保证了对任意一系列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

块则处理有祖父节点的情况。

删除操作的复杂性： 伸展树的删除操作比插入和查找要复杂得多。它通常分两步：

将要删除的节点伸展到根。将该根节点删除后，其左右子树需要重新合并。常见的做法是，将左子树的最大节点（或右子树的最小节点）伸展到左子树的根，然后将原右子树连接到这个新根的右侧。这个过程需要非常小心地处理父指针和根节点的更新。

调试的挑战： 伸展树的动态特性使得其调试变得困难。树的结构在每次操作后都会发生显著变化，单步调试往往难以追踪整个结构的变化。我个人建议，在调试时，可以尝试打印出每次旋转或伸展后树的结构（例如，使用简单的层序遍历打印节点及其父子关系），或者使用可视化工具来帮助理解。

JavaScript的引用特性： JavaScript中对象是按引用传递的。这意味着当你将一个节点赋值给另一个变量时，它们指向的是同一个对象。在修改节点属性时，要清楚这种引用关系，确保修改的是正确的对象实例，并且所有相关的引用都得到了恰当的更新。

总的来说，实现伸展树是对你理解二叉树操作和指针（引用）管理能力的一次很好的考验。耐心、细致和反复测试是成功的关键。

以上就是JS如何实现Splay树？伸展树的旋转的详细内容，更多请关注创想鸟其它相关文章！