我正在做一些leetcode练习https://leetcode.com/problems/design-hashmap/description/尝试使用二叉搜索树作为底层数据结构在C++中实现哈希图。我通过了大部分测试用例，但有一个很长的测试用例表明我给出了错误的答案。然而，测试用例太长了，它没有告诉我我的答案是错误的，所以很难找到问题。对于有二叉搜索树经验的人来说，我的设计有问题吗？感谢您的任何建议！抱歉提出这样的开放式问题。
#define MAXBUCKETS 769 // large prime number that to minimize collisions
class Bucket{ //binary search tree bucket for hashmap
// define what a node looks like
struct node{
int key;
int value;
struct node *left, *right;
};
struct node* root;
// create a new node
struct node* newNode(int newKey, int newValue)
{
struct node* temp = new struct node;
temp->key = newKey;
temp->value = newValue;
temp->left = NULL;
temp->right = NULL;
return temp;
}
// insert a new node given its key
struct node* insertNode(struct node* insertUnder, int newKey, int newVal)
{
// tree is empty, create a new node at this point
// this will make it so that we create roots for empty
// trees, or add as a leaf in the right location
if( insertUnder == NULL)
{
return newNode(newKey, newVal);;
}
// find the right position for this new key and value
if( newKey < insertUnder->key)
{
// smaller keys to the left
insertUnder->left = insertNode(insertUnder->left, newKey, newVal);
}
else if (newKey > insertUnder->key)
{
// bigger keys to the right
insertUnder->right = insertNode(insertUnder->right, newKey, newVal);
}
else
{
// matching key, update value
insertUnder->value = newVal;
}
return insertUnder;
}
// find a node in the tree
int search(struct node* currentNode, int key)
{
if(currentNode == NULL)
{
// empty node, so key is not present
return -1;
}
if(currentNode->key == key)
{
// found key, return its value
return currentNode->value;
}
if(key < currentNode->key)
{
// key could be to the left, search there
return search(currentNode->left, key);
}
else
{
// key could be to the right, search there
return search(currentNode->right, key);
}
}
// find the predecessor of a node
struct node* findSuccessor(struct node* node)
{
// to find the successor of input node, move to the right
// to search the nodes bigger than the input node, and
// then move to the left as many times as you can to find
// the smallest node in that right subree.
node = node->right;
while(node->left)
{
node = node->left;
}
return node;
}
// find the successor of a node
struct node* findPredecessor(struct node* node)
{
// to find the successor of input node, move to the left
// to search the nodes smaller than the input node, and
// then move to the right as many times as you can to find
// the biggest node in that left subree.
node = node->left;
while(node->right)
{
node = node->right;
}
return node;
}
// remove a node from the tree
struct node* removeNode(struct node* node, int key)
{
if(node == NULL)
{
// node is empty, done searching
return NULL;
}
// search through the tree to find the location of the key
if(key < node->key)
{
node->left = removeNode(node->left, key);
}
else if(key > node->key)
{
node->right = removeNode(node->right, key);
}
if(node->key == key)
{
// found the right node
if(node->right == NULL && node->left == NULL) // node is a leaf
{
//simply remove the node
// node = NULL;
delete node;
return NULL;
}
else
{
if(node->right)
{
// node has right child, replace by successor (smallest of right children),
// and delete the successor from the subtree
struct node* successor = findSuccessor(node);
node->key = successor->key;
node->value = successor->value;
node->right = removeNode(successor, successor->key);
}
else //there is a left child
{
// node has no right child, but has a left child,
// so replace by its predecessor (biggest of the left children), and
// delete the predecessor from the subtree
struct node* predecessor = findPredecessor(node);
node->key = predecessor->key;
node->value = predecessor->value;
node->left = removeNode(predecessor, predecessor->key);
}
}
}
return node;
}
public:
Bucket(){
root = NULL;
}
void add(int key, int value)
{
root = insertNode(root, key, value);
}
void remove(int key)
{
root = removeNode(root, key);
}
int findInBucket(int key)
{
return search(root, key);
}
};
class MyHashMap {
Bucket buckets[MAXBUCKETS];
public:
MyHashMap() {
for(int i = 0; i < MAXBUCKETS; i++)
{
buckets[i] = Bucket();
}
}
void put(int key, int value) {
int bucketi = key % MAXBUCKETS;
buckets[bucketi].add(key, value);
}
int get(int key) {
int bucketi = key % MAXBUCKETS;
return buckets[bucketi].findInBucket(key);
}
void remove(int key) {
int bucketi = key % MAXBUCKETS;
buckets[bucketi].remove(key);
}
};
/**
* Your MyHashMap object will be instantiated and called as such:
* MyHashMap* obj = new MyHashMap();
* obj->put(key,value);
* int param_2 = obj->get(key);
* obj->remove(key);
*/
线路
node->right = removeNode(successor, successor->key);
是不正确的，因为
successornode幸运的是，修复很简单：
node->right = removeNode(node->right, successor->key);
将节点替换为有序前驱节点时，需要在另一个分支中修复相同的问题。
node->left = removeNode(node->left, predecessor->key);