伸展树（Splay Tree）是一种自调整的二叉搜索树，由Daniel Sleator和Robert Tarjan在1985年提出。它通过特定的旋转操作（如左旋、右旋和双旋）来重新组织树，使得最近访问的节点更靠近根部，从而在连续的访问中提高性能。C++实现伸展树可以帮助我们理解这种数据结构的内部工作原理，并在实际应用中优化查找、插入和删除等操作的时间复杂度。
在C++中，伸展树的实现通常包括以下几个关键部分：
1. **节点结构**：每个节点应包含键值、指向左子节点和右子节点的指针，以及可能的额外信息，如父节点的指针。例如，在`MysplayTree.h`中，可能会有如下的节点定义：
```cpp
struct Node {
int key;
Node* left;
Node* right;
Node* parent;
};
```
2. **基本操作**：伸展树的核心是它的插入、删除和查找操作，这些操作在执行后都会调用“伸展”操作来调整树的结构。
- **查找**：查找一个节点，沿着中序遍历路径向下，找到目标节点后，通过一系列的旋转将其提升到根部。
- **插入**：首先插入节点到二叉搜索树中，然后对该节点进行伸展操作，使其成为新的根节点。
- **删除**：删除一个节点可能涉及到替换节点、连接子节点和进行伸展操作。在删除后，需要确保被删除节点的替代节点被正确地伸展到根部。
3. **伸展操作**：伸展操作是通过执行一系列的旋转来完成的，包括：
- **左旋**：如果当前节点是其父节点的右孩子，执行左旋将当前节点提升为新的父节点，原父节点变为当前节点的右孩子。
- **右旋**：如果当前节点是其父节点的左孩子，执行右旋将当前节点提升为新的父节点，原父节点变为当前节点的左孩子。
- **双旋**：在某些情况下，可能需要先左旋再右旋或先右旋再左旋，以保持树的平衡。
4. **测试代码**：`MysplayTreeTest.cpp`可能包含了各种测试用例，用于验证伸展树的实现是否正确。这可能包括插入已排序和未排序的序列、查找特定元素、删除元素，以及检查树的结构是否符合伸展树的性质。
5. **效率分析**：伸展树的平均时间复杂度接近于对数，但由于其自调整性，对于频繁访问的元素，查找速度会更快。这是因为它通过伸展操作将最近访问的元素移近根部，使得后续访问更高效。
在实际编程中，理解伸展树的工作原理并能够用C++实现是非常有价值的，尤其是在需要快速访问和更新动态数据集的场景下。通过`MysplayTreeTest.cpp`中的测试，我们可以验证C++实现的伸展树是否满足预期的行为，并进一步优化代码以提高性能。
