Skip to content
search_history_bst_class
🔍 Sistema de historial de búsqueda ordenada (C++ con BST)
Clase extendida con TreeNode y operaciones BST
#include <iostream>
#include <string>
#include <vector>
#include <list>
#include <set>
#include <unordered_map>
#include <algorithm>
struct TreeNode {
std::string val;
TreeNode* left;
TreeNode* right;
TreeNode(const std::string& x) : val(x), left(nullptr), right(nullptr) {}
};
class SearchHistory {
private:
TreeNode* root;
std::list<std::string> chronological;
std::unordered_map<std::string, std::list<std::string>::iterator> termMap;
// Inserta en el BST
TreeNode* insertBST(TreeNode* node, const std::string& term) {
if (!node) return new TreeNode(term);
if (term < node->val)
node->left = insertBST(node->left, term);
else if (term > node->val)
node->right = insertBST(node->right, term);
return node;
}
// Encuentra el nodo mínimo en un BST
TreeNode* findMin(TreeNode* node) {
while (node && node->left)
node = node->left;
return node;
}
// Elimina de un BST
TreeNode* deleteBST(TreeNode* node, const std::string& term) {
if (!node) return nullptr;
if (term < node->val)
node->left = deleteBST(node->left, term);
else if (term > node->val)
node->right = deleteBST(node->right, term);
else {
if (!node->left) {
TreeNode* temp = node->right;
delete node;
return temp;
}
else if (!node->right) {
TreeNode* temp = node->left;
delete node;
return temp;
}
TreeNode* temp = findMin(node->right);
node->val = temp->val;
node->right = deleteBST(node->right, temp->val);
}
return node;
}
void inOrder(TreeNode* node, std::vector<std::string>& result) {
if (!node) return;
inOrder(node->left, result);
result.push_back(node->val);
inOrder(node->right, result);
}
public:
SearchHistory() : root(nullptr) {}
void add(const std::string& term) {
if (termMap.find(term) != termMap.end()) return;
root = insertBST(root, term);
chronological.push_back(term);
termMap[term] = std::prev(chronological.end());
}
std::vector<std::string> getChronological() {
return std::vector<std::string>(chronological.begin(), chronological.end());
}
std::vector<std::string> getAlphabetical() {
std::vector<std::string> result;
inOrder(root, result);
return result;
}
void remove(const std::string& term) {
if (termMap.find(term) == termMap.end()) return;
root = deleteBST(root, term);
chronological.erase(termMap[term]);
termMap.erase(term);
}
};
Want to print your doc?
This is not the way.
This is not the way.
Try clicking the ⋯ next to your doc name or using a keyboard shortcut (
CtrlP
) instead.