1
저는 중복 구성 요소가 트리에 삽입 될 때마다 스스로를 다시 구성하는 자체 주문 바이너리 검색 트리를 만들기 위해 작업하고 있습니다. 내가 도움이 필요한 몇 가지 오류가 있습니다.루트가 변경되지 않는 이유와 잘못된 액세스 오류가 발생하는 이유는 무엇입니까?
처음에는 트리의 루트가 변경되지 않습니다 (문제는 RotateLeft 또는 RotateRight 메서드에 있다고 가정합니다). 내가 읽고있는 샘플 파일이 있고 코드를 살펴볼 때 보이는 것입니다. 그에 따라 모든 것을 구성하십시오. 그러나 첫 번째 복제본이 들어 오면 루트는 이제 더 높은 우선 순위 노드로 변경되지 않습니다.
내가 얻는 두 번째 오류는 나쁜 코드 오류입니다 (아래 코드의 위치에 기록했습니다). 내가 생각하기에 Rotate 메서드 중 하나이기도합니다.
template <class Type>
class BinarySearchTree; //forward declaration so BinaryNode knows about BinarySearchTree
template <class Type>
class BinaryNode{
public:
Type element;
BinaryNode<Type>* left;
BinaryNode<Type>* right;
BinaryNode<Type>* parent;
int priority;
BinaryNode(Type theElement, BinaryNode *lt, BinaryNode* rt, BinaryNode *par = NULL, int pri = 0) :
element(theElement), left(lt), right(rt) , parent(par), priority(pri)
{ }
friend class BinarySearchTree<Type>;
};
사람이 내가 도와 바꿀 수 아무것도 보이지 않는다 : 여기
#ifndef SelfOrganizingTree_SOBTree_h
#define SelfOrganizingTree_SOBTree_h
#include "BinaryNode.h"
#include "bst.h"
template <class T>
class BinaryNode;
template <class T>
class SOBTree: public BinarySearchTree<T> {
public:
SOBTree();
void insert(const T& x);
void remove(const T& x);
bool isEmpty() const;
void printTree() const;
int reportComparisonCount();
double reportCPUTime();
private:
void insert(const T & x, BinaryNode<T> * & t , BinaryNode<T> * & rootNode);
void RotateRight(BinaryNode<T> * & root);
void RotateLeft(BinaryNode<T> * & root);
void printTree(BinaryNode<T> *t) const;
BinaryNode<T> *root;
void balance (BinaryNode<T> * & root);
};
template <class T >
SOBTree<T> :: SOBTree()
{
root = NULL;
}
/**
* Insert x into the tree
*/
template <class T >
void SOBTree<T > :: insert(const T & x)
{
insert(x, root , root);
}
/**
* Internal method to insert into a subtree.
* x is the item to insert.
* t is the node that roots the subtree.
* Set the new root of the subtree.
*/
template <class T>
void SOBTree<T> :: insert(const T & x, BinaryNode<T> * & t , BinaryNode<T> * & rootNode)
{
// BinaryNode<T> *current = t;
if(t == NULL){
t = new BinaryNode<T>(x, NULL, NULL, rootNode);
//cout << t->element << endl;
t->priority++;
}
else if(x < t->element){
//cout << "left" << endl;
insert(x, t->left , t);
}
else if(t->element < x){
//cout << "right" << endl;
insert(x, t->right , t);
}
else{
//cout << "match found" << endl;
t->priority++; // Duplicate; rotate right or left if priority is higher than the root
balance(t);
}
}
template <class T>
void SOBTree<T>::balance (BinaryNode<T> * & rootN){
cout << "root: " << root->element << endl;
if (rootN->parent && rootN->priority > rootN->parent->priority) { //THIS IS WHERE THE BAD ACCESS ERROR IS BEING THROWN
if (rootN->parent->left == rootN) {
RotateLeft(rootN->parent);
balance(rootN->parent);
}else if (rootN->parent->right == rootN){
RotateRight(rootN->parent);
balance(rootN->parent);
}
}
}
template <class T>
void
SOBTree<T>::RotateLeft(BinaryNode<T> * & rootN) {
/*
Let P be Q's left child.
Set P to be the new root.
Set Q's left child to be P's right child.
Set P's right child to be Q.
*/
BinaryNode<T> * oldRoot = rootN;
// perform rotation
rootN = rootN->left;
oldRoot->left = rootN->right;
rootN->right= oldRoot;
}
template <class T>
void
SOBTree<T>::RotateRight(BinaryNode<T> * & rootN) {
/*
Let Q be P's right child.
Set Q to be the new root.
Set P's right child to be Q's left child.
Set Q's left child to be P.
*/
BinaryNode<T> * oldRoot = rootN;
// perform rotation
rootN = rootN->right;
oldRoot->right = rootN->left;
rootN->left = oldRoot;
}
template <class T>
bool SOBTree<T> :: isEmpty() const
{
return root == NULL;
}
/**
* Print the tree contents in sorted order.
*/
template <class T>
void SOBTree<T> :: printTree() const
{
if(isEmpty())
cout << "Empty tree" << endl;
else
printTree(root);
}
template <class T>
void SOBTree<T> :: printTree(BinaryNode<T> *t) const
{
if(t != NULL)
{
printTree(t->left);
cout << t->element << endl;
printTree(t->right);
}else
return;
}
#endif
는 BinaryNode 구조체에 대한 코드?
왜 downvote? – OghmaOsiris