red-black-tree 相关问题

红黑树是一种自平衡二叉搜索树，是计算科学中使用的数据结构，通常用于实现关联数组。

这是一个基本的 RED-BLACK Tree 程序，除了插入和删除之外，它的大部分工作都很好。 #包括 #包括使用命名空间标准；模板这是一个基本的 RED-BLACK Tree 程序，除了插入和删除之外，它的大部分工作都很好。 #include <iostream> #include <cstdlib> using namespace std; template <typename keytype, typename valuetype> //one lesson try to fit for of the functions from the private so that the access can be easier class RBTree{ private: struct Node{ bool color; //color is true for red and false for black int size; Node *left, *right, *parent; keytype key; valuetype val; }; Node* root; Node* newNode(keytype k, valuetype v, bool color = true){ //usually starts with the root and then the leaves can be placed to the left and right Node *newRBNode = new Node; newRBNode->color = color; newRBNode->key = k; newRBNode->left = NULL; newRBNode->right = NULL; newRBNode->parent = NULL; newRBNode->size = 1; //size 1 as it is 1 leaf initially newRBNode->val = v; return newRBNode; } void clearMemory(Node *current) { if (current == NULL){ //uses recursion to go through the tree and delete the leaves return; } clearMemory(current->left); if (current->left != NULL){ free(current->left); } clearMemory(current->right); if (current->right != NULL){ free(current->right); } } int size(Node* current){ if (current == NULL){ return 0; } return current->size; } Node* leftRotate(Node* current){ Node* y = current->right; current->right = y->left; y->left = current; y->color = y->left->color; y->left->color = true; current->size = size(current->left) + size(current->right) + 1; y->size = size(y->left) + size(y->right) + 1; return y; } Node* rightRotate(Node* current){ //conventional rotation from textbook and updates the size Node* y = current->left; current->left = y->right; y->right = current; y->color = y->right->color; y->right->color = true; current->size = size(current->left) + size(current->right) + 1; y->size = size(y->left) + size(y->right) + 1; return y; } Node* copy(Node* current){ //uses recursion to copy Node* node = newNode(current->key, current->val, current->color); if (current->left != NULL){ node->left = copy(current->left); } if(current->right != NULL){ node->right = copy(current->right); } node->size = current->size; return node; } void colorFlip(Node* current){ current->color = !(current->color); //flips the color of the parent and the children (usually one red and two blacks) current->left->color = !(current->left->color); current->right->color = !(current->right->color); } bool isRed(Node* current){ //needs fixing if (current == NULL){ return false; } return (current->color); } Node* Insertion(Node* current, keytype key, valuetype val){ //Messed up if (current == NULL){ Node* test = newNode(key, val); return test; } if (isRed(current->left) && isRed(current->right)){ colorFlip(current); } if (key < current->key){ current->left = Insertion(current->left, key, val); } else if (key > current->key){ current->right = Insertion(current->right, key, val); } else if (current->key == key){ current->val = val; } if (isRed(current->right)){ //if right node is red before the introduced rode then rotation happens current = leftRotate(current); } if (isRed(current->left) && isRed(current->left->left)){ //conflict happens and the rotation starts current = rightRotate(current); } if(isRed(current->right)){ //fixes up the whole tree after deletion current = leftRotate(current); } if (isRed(current->left) && isRed(current->left->left)){ current = rightRotate(current); } if (isRed(current->left) && isRed(current->right)){ colorFlip(current); } current->size = size(current->left) + size(current->right) + 1; return current; } Node* Deletion(Node* current, keytype key){ //Gotta fix it if (key < current->key){ //uses the textboob delete fixation function if (!isRed(current->left) && !isRed(current->left->left)){ colorFlip(current); if (isRed(current->right->left)){ current->right = rightRotate(current->right); current = leftRotate(current); colorFlip(current); } } current->left = Deletion(current->left, key); } else { if (isRed(current->left)){ current = rightRotate(current); } if ((key == current->key) && (current->right == NULL)){ return NULL; } if(!isRed(current->right) && !isRed(current->right->left)){ colorFlip(current); if (isRed(current->left->left)){ current = rightRotate(current); colorFlip(current); } } if (current->key == key){ Node* y = current->right; while(y->left != NULL){ y = y->left; } current->key = y->key; current->val = y->val; current->right = Deletion(current->right, current->key); } else{ current->right = Deletion(current->right, key); } } if(isRed(current->right)){ //fixes up the whole tree after deletion current = leftRotate(current); } if (isRed(current->left) && isRed(current->left->left)){ current = rightRotate(current); } if (isRed(current->left) && isRed(current->right)){ colorFlip(current); } current->size = size(current->left) + size(current->right) + 1; return current; } valuetype* findVal(Node* current, keytype key){ if (current == NULL){ return NULL; } else if (current->key == key){ return &(current->val); } else if(current->key > key){ return findVal(current->left, key); } else if(current->key < key){ return findVal(current->right, key); } return NULL; } keytype Position(Node* current, int sample){ int pos = size(current->left) + 1; if (pos == sample){ return current->key; } else if(sample < pos){ return Position(current->left, sample); } else{ return Position(current->right, sample-pos); } } int Rank(Node* current, keytype key){ if(current == NULL){ return 0; } else if(current->key > key){ return Rank(current->left, key); } else if(current->key < key){ return (size(current->left) + 1 + Rank(current->right, key)); } else if(current->key == key){ return (current->size - size(current->right)); } else{ return 0; } } keytype* find_sucessor(Node* current, keytype K){ Node* successor = NULL; while(current){ if (current->key > K){ successor = current; current = current->left; } else{ current = current->right; } } return &(successor->key); } keytype* find_predecessor(Node* current, keytype K){ Node* predecessor = NULL; while(current){ if (current->key >= K){ current = current->left; } else{ predecessor = current; current = current->right; } } return &(predecessor->key); } void print_preorder(Node* current){ if (current == NULL){ return; } cout << current->key << " "; print_preorder(current->left); print_preorder(current->right); } void print_postorder(Node* current){ if (current == NULL){ return; } print_postorder(current->left); print_postorder(current->right); cout << current->key << " "; } void print_inorder(Node* current){ if (current == NULL){ return; } print_inorder(current->left); cout << current->key << " "; print_inorder(current->right); } public: RBTree(){ root = NULL; } RBTree(keytype k[], valuetype v[], int S){ //black children all of them root = NULL; //wrong gsfsdfsdf int middle = (S-1)/2; // for (int i = middle; i > 0; i--){ //insert from half till zero then half to full // root = Insertion(root, k[i], v[i]); // root->color = false; // } // for (int i = 0; i < S; i++){ // root = Insertion(root, k[i], v[i]); // root->color = false; //false is black and true is red // } root = Insertion(root, k[middle], v[middle]); root->color = false; for (int i = 1; i <= middle; i++){ root = Insertion(root, k[middle-i], v[middle-i]); root->color = false; root = Insertion(root, k[middle+i], v[middle+i]); root->color = false; } if (((2*middle)) != (S-1)){ root = Insertion(root, k[S-1], v[S-1]); root->color = false; } } RBTree(const RBTree<keytype, valuetype> &A){ root = copy(A.root); } RBTree<keytype, valuetype>& operator=(const RBTree<keytype, valuetype> &A){ root = copy(A.root); return *this; } ~RBTree(){ clearMemory(root); free(root); } valuetype* search(keytype k){ return findVal(root,k); } void insert(keytype k, valuetype v){ root = Insertion(root, k, v); root->color = false; } int remove(keytype k){ if (search(k) == NULL){ return 0; } int node = size(root); root = Deletion(root, k); return (node - size(root)); } int rank(keytype k){ return Rank(root,k); } keytype select(int pos){ return Position(root, pos); } keytype* successor(keytype k){ return find_sucessor(root, k); } keytype* predecessor(keytype k){ return find_predecessor(root, k); } int size(){ return size(root); } void preorder(){ print_preorder(root); cout << endl; } void inorder(){ print_inorder(root); cout << endl; } void postorder(){ print_postorder(root); cout << endl; } }; 当我尝试插入：A"、"B"、"C"、"D"、"E"、"F"、"G"、"H"、"I"、"K"时，我得到了顺序正确。但后序和前序不正确。我该怎么做才能正确输出其中的 3 个视图？非常感谢您的帮助。

c++ red-black-tree red-black-tree-insertion

回答 0 投票 0

调试平衡二叉搜索树的过程

我已经实现了一个红黑搜索树，目前正在研究以下功能：目前正在使用以下功能：向树中添加新节点打印树： -- 对于...

pointers freepascal red-black-tree

回答 0 投票 0

算法导论中提到的红黑删除算法的问题，CLRS第三版。

RB-DELETE(T, z) 1 y = z 2 y-original-color = y.color 3 if z.left == T.nil 4 x = z.right 5 RB-TRANSPLANT(T, z, z.right) 6 elif z.right == T.nil 7 x = z.left 8 RB-TRANSPLANT(T, z, ...

algorithm data-structures red-black-tree

回答 1 投票 0

确定红黑树中的节点颜色

我正在阅读有关红黑树的文章，并且我知道节点可以是红色或黑色。规则说：1）每个节点都有一种颜色-红色或黑色。 2）树的根总是黑色的。 3）...

data-structures red-black-tree red-black-tree-insertion

回答 1 投票 1

C中的分配节点内存（RED-BLACK树）

我正在尝试使用带有（void *）数据的节点结构（节点保存的数据是generalint，字符串，struct Vector等）来构建带有节点结构的RED-BLACK树。我能够删除节点完全向上...

c memory valgrind red-black-tree

回答 1 投票 0

每个节点多少位

[这个问题来自算法4的练习。我在这里粘贴如下：3.3.19每个节点1位的颜色，我们可以表示2、3和4节点。每个节点需要多少位...