C++ AVLツリーの削除

Question

したがって、テキストファイルから入力を受け取り、AVLツリーでいくつかの操作を行いたいとします。私は挿入を実装することができましたが、削除のためのソリューションを私の心の中に構築することはできません。手伝って頂けますか？ここにコードがあります。

#include<iostream> 
#include<cstdio> 
#include<sstream> 
#include<algorithm> 
#include <fstream> 
#include <stdlib.h> 
#include <array> 
#include <ctime> 

    using namespace std; 

    struct node 
    { 
     int data; 
     int height; 
     struct node *leftchild; 
     struct node *rightchild; 

    }*root; 

class avlTree 
    { 
     public: 
     int height(node *); 
     int difference(node *); 
     node *rrtraversal(node *); 
     node *lltraversal(node *); 
     node *lrtraversal(node *); 
     node *rltraversal(node *); 
     node* balance(node *); 
     node* insert(node *, int); 
     void display(node *, int); 
     node *del(node *, int); 

     avlTree() 
     { 
     root = NULL; 
     } 
}; 

int avlTree::height(node *temp) 
{ 
    int h = 0; 
    if (temp != NULL) 
    { 
     int l_height = height (temp->leftchild); 
     int r_height = height (temp->rightchild); 
     int max_height = max (l_height, r_height); 
     h = max_height + 1; 
    } 
    return h; 
} 

int avlTree::difference(node *temp) 
{ 
    int l_height = height (temp->leftchild); 
    int r_height = height (temp->rightchild); 
    int b_factor= l_height - r_height; 
    return b_factor; 
} 

node *avlTree::rrtraversal(node *parent) 
{ 
    node *temp; 
    temp = parent->rightchild; 
    parent->rightchild = temp->leftchild; 
    temp->leftchild = parent; 
    return temp; 
} 

node *avlTree::lltraversal(node *parent) 
{ 
    node *temp; 
    temp = parent->leftchild; 
    parent->leftchild = temp->rightchild; 
    temp->rightchild = parent; 
    return temp; 
} 

node *avlTree::lrtraversal(node *parent) 
{ 
    node *temp; 
    temp = parent->leftchild; 
    parent->leftchild = rrtraversal (temp); 
    return lltraversal (parent); 
} 


node *avlTree::rltraversal(node *parent) 
{ 
    node *temp; 
    temp = parent->rightchild; 
    parent->rightchild = lltraversal (temp); 
    return rrtraversal (parent); 
} 


node *avlTree::balance(node *temp) 
{ 
    int bal_factor = difference (temp); 
    if (bal_factor > 1) 
    { 
     if (difference (temp->leftchild) > 0) 
      temp = lltraversal (temp); 
     else 
      temp = lrtraversal (temp); 
    } 
    else if (bal_factor < -1) 
    { 
     if (difference (temp->rightchild) > 0) 
      temp = rltraversal (temp); 
     else 
      temp = rrtraversal (temp); 
    } 
    return temp; 
} 


node *avlTree::insert(node *root, int value) 
{ 
    if (root == NULL) 
    { 
     root = new node; 
     root->data = value; 
     root->leftchild = NULL; 
     root->rightchild = NULL; 
     return root; 
    } 
    else if (value < root->data) 
    { 
     root->leftchild = insert(root->leftchild, value); 
     root = balance (root); 
    } 
    else if (value >= root->data) 
    { 
     root->rightchild = insert(root->rightchild, value); 
     root = balance (root); 
    } 
    return root; 
} 

void avlTree::display(node *ptr, int level) 
{ 
    int i; 
    if (ptr!=NULL) 
    { 
     display(ptr->rightchild, level + 1); 
     printf("\n"); 
     for (i = 0; i < level && ptr != root; i++) 
      cout<<"  "; 
     cout<<ptr->data; 
     display(ptr->leftchild, level + 1); 
    } 
} 

node *avlTree::del(node *root, int x) 
{ 
    node *d; 

    if (x < root->data){ 
     del(root->leftchild,x); 

    } 
    else if (x > root->data){ 
     del(root->rightchild,x); 


    } 
    else if ((root->leftchild == NULL) && (root->rightchild == NULL)) 
    { 
     d=root; 
     free(d); 
     root=NULL; 

    } 
    else if (root->leftchild == NULL) 
    { 
     d=root; 
     free(d); 
     root= root->rightchild; 

    } 
    else if (root->rightchild == NULL) 
    { 
     d=root; 
     root=root->leftchild; 
     free(d); 

    } 

    return root; 

} 

int main() 
{ 

    ifstream myFile("file.txt"); 
    int a = 0; 
    std::array<string,512> arrayTest; 
    int index = 0; 
    string content; 
    avlTree avl; 

    while (myFile >> content){ 
     arrayTest[index] = content; 
     index++;  
    } 

    clock_t startTime = clock(); 

    for(a = 0; a < arrayTest.size();a++){ 
     if(arrayTest[a] == "i"){ 
     root = avl.insert(root, std::stoi(arrayTest[a+1])); 
     } 
    } 

    avl.display(root,1); 

    clock_t endTime = clock(); 
    clock_t clockTicksTaken = endTime - startTime; 
    double timeInSeconds = clockTicksTaken/(double) CLOCKS_PER_SEC; 

    cout << "\n\n" << timeInSeconds << " secs\n"; 

} 

ファイルの内容は次のとおりです。 i 1 i 2 i 3 i 4 i 5 d 3

プログラムがiを見ると、挿入操作を行います。同様に、dを見ると、削除操作を行います。

Answer 1

無料（）機能を試しましたか？

free(node);