0
삽입을 위해 AVL 트리에서 작업 해 왔습니다. 인서트는 제대로 작동하지만 시도한 모든 회전은 제대로 작동하지 않습니다. 내 밸런싱을위한 다른 위치를 시도해 왔고 각 삽입 후에 회전하여 시도 할 수도 있지만 작동 여부를 확인하기 위해 로테이션을 시도하지는 않습니다. 왜 내 로테이션이 효과가 없는지에 대한 도움은 크게 감사 할 것입니다.AVL 트리 회전 관련 문제
헤더 :
#ifndef LINKEDBINARYTREE_H
#define LINKEDBINARYTREE_H
#include <iostream>
#include <string>
using namespace std;
class LinkedBinaryTree {
private:
struct Node {
string word;
Node* left;
Node* right;
Node* parent;
int wordCount;
int height;
Node() : word(), left(NULL), right(NULL), parent(NULL), wordCount(1), height(1) {}
Node(string s, Node* l, Node* r, Node* p) {
word = s;
left = NULL;
right = NULL;
parent = p;
wordCount = 1;
height = 1;
}
};
Node* _root;
public:
LinkedBinaryTree();
~LinkedBinaryTree();
void insertNode(Node* node, string word);
void insert(string word);
void display(Node* ptr, int level);
Node* root();
void inOrder(Node* node);
void rightRotate(Node* node);
void leftRotate(Node* node);
void rightLeftRotate(Node* node);
void leftRightRotate(Node* node);
int avlNum(Node* node);
int height(Node* node);
int bfactor(Node* node);
void fixHeight(Node* node);
void balance(Node* node);
int n;
};
#endif
통화 당 :
#include "LinkedBinaryTree.h"
#include <algorithm>
void LinkedBinaryTree::inOrder(Node * node)
{
if (node == NULL)
return;
inOrder(node->left);
cout << node->word << " " << avlNum(node) << " : " ;
inOrder(node->right);
}
void LinkedBinaryTree::rightRotate(Node* node)
{
Node* temp;
temp = node->left;
node->left = temp->right;
temp->right = node;
temp->parent = node->parent;
node = temp;
if (temp->parent = NULL) {
_root = temp;
}
fixHeight(node);
fixHeight(node->right);
fixHeight(node->left);
}
void LinkedBinaryTree::leftRotate(Node * node)
{
Node* temp;
temp = node->right;
node->right = temp->left;
temp->left = node;
temp->parent = node->parent;
node = temp;
if (temp->parent = NULL) {
_root = temp;
}
fixHeight(node);
fixHeight(node->right);
fixHeight(node->left);
}
void LinkedBinaryTree::rightLeftRotate(Node * node)
{
rightRotate(node->left);
leftRotate(node);
}
void LinkedBinaryTree::leftRightRotate(Node * node)
{
leftRotate(node->right);
rightRotate(node);
}
int LinkedBinaryTree::height(Node * node)
{
int h = 0;
if (node != NULL) {
h = node->height;
}
return h;
}
int LinkedBinaryTree::bfactor(Node * node)
{
return height(node->right) - height(node->left);
}
void LinkedBinaryTree::fixHeight(Node * node)
{
int hl = height(node->left);
int hr = height(node->right);
node->height = (hl > hr ? hl : hr) + 1;
}
int LinkedBinaryTree::avlNum(Node * node)
{
int leftH = height(node->left);
int rightH = height(node->right);
int avlNum = rightH - leftH;
return avlNum;
}
LinkedBinaryTree::LinkedBinaryTree()
{
_root = NULL;
}
LinkedBinaryTree::~LinkedBinaryTree()
{
}
void LinkedBinaryTree::insertNode(Node* node, string word)
{
if (word < node->word) {
if (node->left != NULL)
insertNode(node->left, word);
else {
node->left = new Node(word, NULL, NULL, node);
}
}
else if (word > node->word)
{
if (node->right != NULL)
insertNode(node->right, word);
else {
node->right = new Node(word, NULL, NULL, node);
}
}
else if (word == node->word) {
node->wordCount++;
}
balance(node);
}
void LinkedBinaryTree::insert(string word) {
if (_root == NULL) {
_root = new Node(word, NULL, NULL, NULL);
n++;
}
else {
insertNode(_root, word);
n++;
}
}
void LinkedBinaryTree::display(Node* ptr, int level)
{
int i;
if (ptr != NULL)
{
display(ptr->right, level + 1);
printf("\n");
if (ptr == _root)
cout << "Root -> ";
for (i = 0; i < level && ptr != _root; i++)
cout << " ";
cout << ptr->word;
display(ptr->left, level + 1);
}
}
LinkedBinaryTree::Node * LinkedBinaryTree::root()
{
return _root;
}
void LinkedBinaryTree::balance(Node* node)
{
fixHeight(node);
if (bfactor(node) == 2) {
if (bfactor(node->right) < 0)
rightRotate(node->right);
else
leftRotate(node);
}
if (bfactor(node) == 2) {
if (bfactor(node->left) > 0)
leftRotate(node->left);
else
rightRotate(node);
}
}
주 :
#include "LinkedBinaryTree.h"
#include <string>
int main() {
LinkedBinaryTree t;
t.insert("Yes");
t.insert("No");
t.insert("Maybe");
t.insert("Hopefully");
t.insert("Absolutely");
t.display(t.root(), 1);
cout << endl;
cout << endl;
t.inOrder(t.root());
system("PAUSE");
return EXIT_SUCCESS;
}
아, 고맙습니다. 내 코드에서 이러한 변경 사항을 만들었지 만 여전히 문제를 수정하지는 않습니다. "Yes"는 항상 루트가됩니다. 회전이 시작되면 아무 것도 회전하지 않아도 트리 루트를 변경해야하기 때문에 이해할 수없는 일은 중요하지 않습니다. – NeerP84
@ NeerP84'if (temp-> parent == NULL)'을'if (temp-> parent == NULL)'로 수정 했습니까? – 1201ProgramAlarm
고쳐 주셔서 감사합니다. 나는 네 번째 삽입 후 노드를 잃어 가고있다. – NeerP84