伸展树的旋转操作分为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
到根的路径，并且其局部平衡效果也比两次单旋叠加要好。它避免了单旋可能导致的某些子树失衡问题。
通过这些特定的组合旋转，伸展树保证了对任意一系列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树？伸展树的旋转的详细内容，更多请关注创想鸟其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 chuangxiangniao@163.com 举报，一经查实，本站将立刻删除。
发布者：程序猿，转转请注明出处：https://www.chuangxiangniao.com/p/1515938.html
微信扫一扫 
支付宝扫一扫 
