构造哈希表II

继上一篇构造哈希表的文章以后, 又碰到了一个需要构造哈希表的问题, 只不过此时的哈希表已经从unordered_map换为了unordered_set.

信心满满地想用刚学的利用桶和链表构造unordered_map的方法来秒了这个问题, 结果虽然还可以, 跑了28个案例耗时56ms…… 然而, 当我看到又有大神提出更强的算法时, 真是佩服得五体投地, mark一下, 他是通过构造一棵二叉查找树来完成的, 在释放内存时也很值得学习, 在删除节点之前先把左子树和右子树删除~ 代码如下所示:

// https://www.geeksforgeeks.org/fast-io-for-competitive-programming/
// https://codeforces.com/blog/entry/10297
// People are not actually implementing any form of hash set, so I use tricks
static const int _ = []() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
return 0;
}();

struct MyHashSetNode {
int val;
MyHashSetNode *left, *right;

MyHashSetNode(int v) : val(v), left(nullptr), right(nullptr) {}
~MyHashSetNode() {
if(left  != nullptr) delete left;
if(right != nullptr) delete right;
}
};

class MyHashSetTree {
private:
MyHashSetNode *root;
public:
MyHashSetTree() : root(nullptr) {}
~MyHashSetTree() {
if(root != nullptr)
delete root; // traverses through destructors
}

MyHashSetNode *Insert(int x, MyHashSetNode *parent) {
MyHashSetNode *result = parent;

if (parent == nullptr) {
result = new MyHashSetNode(x);
} else if (x < parent->val) {
parent->left = Insert(x, parent->left);
} else if (x > parent->val) {
parent->right = Insert(x, parent->right);
} else {
return nullptr; // duplicate, add should not comply
}

return result;
}

bool Insert(int x) {
if(Find(x) != nullptr)
return false;

root = Insert(x, root);
return true;
}

MyHashSetNode *Find(int x, MyHashSetNode *parent) {
MyHashSetNode *current = parent;
int currentValue;

while (current != nullptr) {
currentValue = current->val;
if (x < currentValue) {
current = current->left;
} else if (x > currentValue) {
current = current->right;
} else {
return current;
}
}

return nullptr;
}

MyHashSetNode *Find(int x) {
if (root != nullptr)
return Find(x, root);

return nullptr;
}

MyHashSetNode *FindMin(MyHashSetNode *parent) {
MyHashSetNode *current = parent;
MyHashSetNode *left = nullptr;

if (current != nullptr) {
while ((left = current->left) != nullptr)
current = left;
}

return current;
}

MyHashSetNode *RemoveMin(MyHashSetNode *parent) {
if (parent == nullptr) {
return nullptr;
} else if (parent->left != nullptr) {
parent->left = RemoveMin(parent->left);
return parent;
} else {
MyHashSetNode *result = parent->right;

parent->right = parent->left = nullptr;
delete parent;
return result;
}
}

MyHashSetNode *Remove(int x, MyHashSetNode *parent) {
MyHashSetNode *current = parent;
MyHashSetNode *left = nullptr;
MyHashSetNode *right = nullptr;
int currentValue;

if (current != nullptr) {
left = current->left;
right = current->right;
currentValue = current->val;
}

if (current == nullptr) {
return nullptr;
} else if (x < currentValue) {
current->left = Remove(x, left);
} else if (x > currentValue) {
current->right = Remove(x, right);
} else if (left != nullptr && right != nullptr) {
current->val = FindMin(right)->val;
current->right = RemoveMin(right);
} else {
current = (left != nullptr) ? left : right;

parent->right = parent->left = nullptr;
delete parent;
}

return current;
}

bool Remove(int x) {
if(Find(x) == nullptr)
return false;

root = Remove(x, root);
return true;
}
};

class MyHashSet {
private:
MyHashSetTree tree;
public:
/** Initialize your data structure here. */
MyHashSet() {

}

void add(int key) {
tree.Insert(key);
}

void remove(int key) {
tree.Remove(key);
}

/** Returns true if this set contains the specified element */
bool contains(int key) {
return tree.Find(key) != nullptr;
}
};