Rotation in einem Red/Black Tree.



  • Einen schönen guten Abend!

    So, ich habe eine Frage zur Rotation in einem Rot-Schwarz Baum. Die Theorie ist mir sehr bekannt. Bekomme es aber einfach nicht hin, die Funktion rotate() zu programmieren.
    Lokal gesehen, bekomme ich die Rotation hin, aber irgendwie zerstöre ich mir den Baum damit.

    Zum Kontext, hier meine add() Methode. Die Splittfunktion (top down)färbt nur einen 4er Knoten im Baum um.

    void Tree::addNode(std::string name, int age, double income, int postcode) {
    
    	TreeNode* newNode = new TreeNode;
    	newNode->setName(name);
    	newNode->setPostCode(postcode);
    	newNode->setAge(age);
    	newNode->setNodeChronoID(currentNodeChronologicalID);
    	currentNodeChronologicalID = currentNodeChronologicalID + 1;
    	newNode->setNodeOrderID(calc_Node_ID(age, postcode, income));
    
    	TreeNode* tmp = nullptr;   
    	TreeNode* tmp1 = nullptr;
    	TreeNode* tmp2 = nullptr;
    
    	int pathLen = 0;
    	std::vector <TreeNode*> q;
    
    	if (anker == nullptr) {
    		anker = newNode;
    		return;
    	}
    
    	TreeNode* ptr = anker;
    	TreeNode* parent = nullptr;
    	newNode->setRed(true);
    
    	while (ptr != nullptr) {
    		parent = ptr;
    		split4Node(parent);
    
    
    		if (newNode->getNodeOrderID() < ptr->getNodeOrderID()) {
    			ptr = ptr->getLeft();
    			q.push_back(parent);
    		}
    		else {
    			ptr = ptr->getRight();
    			q.push_back(parent);
    		}
    	}
    
    	if (newNode->getNodeOrderID() < parent->getNodeOrderID()) {
    		parent->setLeft(newNode);
    		newNode->setParent(parent);
    	}
    	else {
    		parent->setRight(newNode);
    		newNode->setParent(parent);
    	}
    
    	q.push_back(newNode);
    	// Pfadlaenge bestimmen
    	pathLen = q.size() - 1;
    
    	if (pathLen >= 3) {
    		for (size_t i = pathLen; i > 1; i--) {
    
    			//Überprüfen rot-rot-schwarz bottom up !!
    
    			if ((q[i]->getRed()) && (q[i - 1]->getRed()) && (!q[i - 2]->getRed())) {
    
    				tmp = q[i - 2]; // schwarz
    				tmp1 = q[i - 1]; //rot
    				tmp2 = q[i];    // rot
    
    				//Vier Fälle
    				// wenn der tmp2 < tmp1 < tmp ist, keine doppelte Rotation -> kein Knick
    				if (tmp2->getNodeOrderID() < tmp1->getNodeOrderID() && tmp1->getNodeOrderID() < tmp->getNodeOrderID()) {
    
    					rotateRight(tmp);
    
    
    				}
    				else if (tmp2->getNodeOrderID() > tmp1->getNodeOrderID() && tmp1->getNodeOrderID() > tmp->getNodeOrderID()) {
    
    					//rotateLeft(tmp);
    
    				}
    				//Dopple Rotation
    				else if (tmp->getNodeOrderID() > tmp1->getNodeOrderID() && tmp1->getNodeOrderID() < tmp2->getNodeOrderID()) {
    					
    					//rotateRight(tmp);
    					//rotateLeft(tmp);
    				}
    
    				else if (tmp->getNodeOrderID() < tmp1->getNodeOrderID() && tmp1->getNodeOrderID() > tmp2->getNodeOrderID()) {
    
    					//rotateLeft(tmp);
    					//rotateRight(tmp);
    				}
    			}
    
    		}
    
    	}
    }
    

    Hier meine Rotationfunktion:

    void Tree::rotateRight(TreeNode*& node) {
    
    
    	TreeNode* ptr = node->getLeft();
    
    	node->setLeft(ptr->getRight());
    	ptr->setRight(node);
    
    	ptr->setRed(node->getRed());
    	node->setRed(true);
    
    	node = ptr;
    
    	
    }
    

Anmelden zum Antworten