26、跳表
在C++标准库中，std::map 和 std::set 是使用红黑树作为底层数据结构的容器。
红黑树是一种自平衡二叉搜索树，能够保证插入、删除和查找操作的时间复杂度为O(log n)。
以下是一些使用红黑树的C++标准库容器：
std::map：一种关联容器，存储键值对，并根据键进行排序。std::set：一种关联容器，存储唯一的键，并根据键进行排序。
示例代码：
#include <iostream>
#include <map>
#include <set>int main() {// 使用std::mapstd::map<int, std::string> myMap;myMap[1] = "one";myMap[2] = "two";myMap[3] = "three";for (const auto& pair : myMap) {std::cout << pair.first << ": " << pair.second << std::endl;}// 使用std::setstd::set<int> mySet;mySet.insert(1);mySet.insert(2);mySet.insert(3);for (const auto& element : mySet) {std::cout << element << std::endl;}return 0;
}
在这个示例中，std::map 和 std::set 都使用红黑树作为底层数据结构来存储和管理元素。
以下是一个简单的跳表实现示例：
#include <iostream>
#include <cstdlib>
#include <ctime>
#include <vector>class SkipListNode {
public:int value;std::vector<SkipListNode*> forward;SkipListNode(int val, int level) : value(val), forward(level, nullptr) {}
};class SkipList {
private:int maxLevel;float probability;SkipListNode* header;int randomLevel() {int level = 1;while (((float)std::rand() / RAND_MAX) < probability && level < maxLevel) {level++;}return level;}public:SkipList(int maxLevel, float probability) : maxLevel(maxLevel), probability(probability) {header = new SkipListNode(-1, maxLevel);}void insert(int value) {std::vector<SkipListNode*> update(maxLevel, nullptr);SkipListNode* current = header;for (int i = maxLevel - 1; i >= 0; i--) {while (current->forward[i] != nullptr && current->forward[i]->value < value) {current = current->forward[i];}update[i] = current;}int level = randomLevel();SkipListNode* newNode = new SkipListNode(value, level);for (int i = 0; i < level; i++) {newNode->forward[i] = update[i]->forward[i];update[i]->forward[i] = newNode;}}bool search(int value) {SkipListNode* current = header;for (int i = maxLevel - 1; i >= 0; i--) {while (current->forward[i] != nullptr && current->forward[i]->value < value) {current = current->forward[i];}}current = current->forward[0];return current != nullptr && current->value == value;}void display() {for (int i = 0; i < maxLevel; i++) {SkipListNode* node = header->forward[i];std::cout << "Level " << i + 1 << ": ";while (node != nullptr) {std::cout << node->value << " ";node = node->forward[i];}std::cout << std::endl;}}
};int main() {std::srand(std::time(0));SkipList list(4, 0.5);list.insert(3);list.insert(6);list.insert(7);list.insert(9);list.insert(12);list.insert(19);list.insert(17);list.insert(26);list.insert(21);list.insert(25);list.display();std::cout << "Search for 19: " << (list.search(19) ? "Found" : "Not Found") << std::endl;std::cout << "Search for 15: " << (list.search(15) ? "Found" : "Not Found") << std::endl;return 0;
}
这个示例实现了一个简单的跳表，支持插入和搜索操作。可以根据需要扩展这个实现。