1

更新：「doAVLBalance」でメンバー関数「isBalanced（）」、「isRightHeavy（）」、「isLeftHeavy」を認識できないため、「Balancing」を機能させることができません。そして、私は理由がわかりません！Sashの例（3番目の回答）を正確に試しましたが、「減速に互換性がありません」と表示され、修正できませんでした...それで、自分のやり方で試してみました...そして、これらのメンバー関数が存在しないと表示されます。彼らは明らかにそうします。

「エラー：クラス「IntBinaryTree：TreeNode」にはメンバー「isRightHeavy」がありません。過去4時間試行した後、スタックします:(。以下の更新されたコード、助けていただければ幸いです!!

文字列ベースの二分探索木を作成していて、それを「バランスのとれた」木にする必要があります。どうすればよいですか？*助けてください!! 前もって感謝します！

BinarySearchTree.cpp：

    bool IntBinaryTree::leftRotation(TreeNode *root)
    {
        //TreeNode *nodePtr = root;  // Can use nodePtr instead of root, better?
        // root, nodePtr, this->?

        if(NULL == root)
        {return NULL;}

        TreeNode *rightOfTheRoot = root->right;
        root->right = rightOfTheRoot->left;
        rightOfTheRoot->left = root;

        return rightOfTheRoot;
    }

    bool IntBinaryTree::rightRotation(TreeNode *root)
    {
        if(NULL == root)
        {return NULL;}
        TreeNode *leftOfTheRoot = root->left;
        root->left = leftOfTheRoot->right;
        leftOfTheRoot->right = root;

        return leftOfTheRoot;
    }

    bool IntBinaryTree::doAVLBalance(TreeNode *root)
    {


        if(NULL==root)
            {return NULL;}
        else if(root->isBalanced()) // Don't have "isBalanced"
            {return root;}

        root->left = doAVLBalance(root->left);
        root->right = doAVLBalance(root->right);

        getDepth(root); //Don't have this function yet

        if(root->isRightHeavy()) // Don't have "isRightHeavey"
        {
            if(root->right->isLeftheavey())
            {
                root->right = rightRotation(root->right);
            }
            root = leftRotation(root);
        }
        else if(root->isLeftheavey()) // Don't have "isLeftHeavey"
        {
            if(root->left->isRightHeavey())
            {
                root->left = leftRotation(root->left);
            }
            root = rightRotation(root);
        }
        return root;
    }

    void IntBinaryTree::insert(TreeNode *&nodePtr, TreeNode *&newNode)
    {
        if(nodePtr == NULL)
            nodePtr = newNode;                  //Insert node
        else if(newNode->value < nodePtr->value)
            insert(nodePtr->left, newNode);     //Search left branch
        else
            insert(nodePtr->right, newNode);    //search right branch
    }

//
// Displays the number of nodes in the Tree


int IntBinaryTree::numberNodes(TreeNode *root)
{
    TreeNode *nodePtr = root;

    if(root == NULL)
        return 0;

    int count = 1; // our actual node
    if(nodePtr->left !=NULL)
    { count += numberNodes(nodePtr->left);
    }
    if(nodePtr->right != NULL)
    {
        count += numberNodes(nodePtr->right);
    }
    return count;
} 

    // Insert member function

    void IntBinaryTree::insertNode(string num)
    {
        TreeNode *newNode; // Poitner to a new node.

        // Create a new node and store num in it.
        newNode = new TreeNode;
        newNode->value = num;
        newNode->left = newNode->right = NULL;

        //Insert the node.
        insert(root, newNode);
    }

    // More member functions, etc.

BinarySearchTree.h：

class IntBinaryTree
{
private:
    struct TreeNode
    {
        string value; // Value in the node
        TreeNode *left; // Pointer to left child node
        TreeNode *right; // Pointer to right child node
    };

    //Private Members Functions
    // Removed for shortness
    void displayInOrder(TreeNode *) const;


public:
    TreeNode *root;
    //Constructor
    IntBinaryTree()
        { root = NULL; }
    //Destructor
    ~IntBinaryTree()
        { destroySubTree(root); }

    // Binary tree Operations
    void insertNode(string);
    // Removed for shortness

    int numberNodes(TreeNode *root);
    //int balancedTree(string, int, int); // TreeBalanced

    bool leftRotation(TreeNode *root);
    bool rightRotation(TreeNode *root);
    bool doAVLBalance(TreeNode *root); // void doAVLBalance();
    bool isAVLBalanced();

    int calculateAndGetAVLBalanceFactor(TreeNode *root);

    int getAVLBalanceFactor()
    {
        TreeNode *nodePtr = root; // Okay to do this? instead of just
        // left->mDepth
        // right->mDepth

        int leftTreeDepth = (left !=NULL) ? nodePtr->left->Depth : -1;
        int rightTreeDepth = (right != NULL) ? nodePtr->right->Depth : -1;
        return(leftTreeDepth - rightTreeDepth);
    }

    bool isRightheavey() { return (getAVLBalanceFactor() <= -2); }

    bool isLeftheavey() { return (getAVLBalanceFactor() >= 2); }


    bool isBalanced()
    {
        int balanceFactor = getAVLBalanceFactor();
        return (balanceFactor >= -1 && balanceFactor <= 1);
    }


    int getDepth(TreeNode *root); // getDepth

    void displayInOrder() const
        { displayInOrder(root); }
    // Removed for shortness
};
4

3 に答える 3

1

これを行うには多くの方法がありますが、実際にはすべてではないことをお勧めします。文字列のBSTを保存する場合は、はるかに優れたオプションがあります。

  1. 事前に作成された二分探索木クラスを使用します。C ++ std :: setクラスは、平衡二分探索木と同じ時間保証を提供し、多くの場合、そのように実装されます。自分のBSTをローリングするよりもはるかに使いやすいです。

  2. 代わりにトライを使用してください。トライデータ構造は、文字列のBSTよりも単純で効率的であり、バランシングをまったく必要とせず、BSTよりも高速です。

本当にバランスの取れたBSTを作成する必要がある場合は、多くのオプションがあります。バランシングを使用するほとんどのBST実装は非常に複雑であり、気の弱い人向けではありません。実装がかなり簡単な2つのバランスの取れたBST構造である、treapまたはsplayツリーのいずれかを実装することをお勧めします。これらは両方とも上記のコードよりも複雑であり、この短いスペースでは実装を提供できませんが、これらの構造をWikipediaで検索すると、続行する方法について多くのアドバイスが得られるはずです。

お役に立てれば！

于 2011-08-02T05:21:44.060 に答える
1

残念ながら、私たちプログラマーは文字通りの獣です。

それを「バランスのとれた」木にします。

「バランス」はコンテキストに依存します。導入データ構造クラスは通常、最大深度のノードと最小深度のノードの差が最小化されたときに「バランスが取れている」ツリーを指します。ただし、Sir Templatetypedefが述べているように、スプレー木は平衡木と見なされます。これは、一度に少数のノードが頻繁にアクセスする場合に、ツリーのバランスをかなりうまく取ることができるためです。これは、これらの場合、従来のバイナリツリーよりもスプレーツリーのデータを取得するために必要なノードトラバーサルが少ないためです。一方、アクセスごとの最悪の場合のパフォーマンスは、リンクリストと同じくらい悪い場合があります。

リンクリストといえば...

それ以外の点では「バランシング」がないので、私が読んだリンクリストと同じであり、目的を打ち破ります。

それは悪いことかもしれませんが、ランダム化された挿入の場合はそうではありません。すでに並べ替えられたデータを挿入する場合、ほとんどのバイナリ検索ツリーの実装は、肥大化して順序付けられたリンクリストのようなデータを格納します。ただし、それは、ツリーの片側を継続的に構築しているためです。（1、2、3、4、5、6、7などを二分木に挿入することを想像してください。紙で試してみてください。）

理論的に最悪の場合に保証された意味でバランスを取る必要がある場合は、赤黒木を調べることをお勧めします。（グーグルそれ、2番目のリンクはかなり良いです。）

この特定のシナリオで合理的な方法でバランスをとる必要がある場合は、整数インデックスと適切なハッシュ関数を使用します。そうすれば、余分なコードなしでバランスが確率的に発生します。つまり、比較関数を、現在の関数ではなく、hash（strA）<hash（strB）のように見せます。（この場合の迅速で効果的なハッシュについては、FNVハッシュを調べてください。最初にGoogleでヒットします。有用なコードが表示されるまで下に移動します。）必要に応じて、実装効率の詳細について心配することができます。（たとえば、文字列の1つは変更されないため、比較するたびに両方のハッシュを実行する必要はありません。）

あなたがそれで逃げることができるならば、あなたが時間の危機に瀕していて何か速いものが欲しいなら、私は後者を強くお勧めします。それ以外の場合、赤黒木は、高さのバランスが取れた独自の二分木を転がす必要がある場合に実際に非常に役立つため、価値があります。

最後に、上記のコードに対処するには、以下のコードのコメントを参照してください。

int IntBinaryTree::numberNodes(TreeNode *root)
{
    if(root = NULL) // You're using '=' where you want '==' -- common mistake.
                    // Consider getting used to putting the value first -- that is,
                    // "NULL == root". That way if you make that mistake again, the
                    // compiler will error in many cases.
        return 0;
    /*
    if(TreeNode.left=null && TreeNode.right==null)  // Meant to use '==' again.
    { return 1; }

    return numberNodes(node.left) + numberNodes(node.right);
    */

    int count = 1; // our actual node
    if (left != NULL)
    {
        // You likely meant 'root.left' on the next line, not 'TreeNode.left'.
        count += numberNodes(TreeNode.left);
        // That's probably the line that's giving you the error.
    }
    if (right != NULL)
    {
        count += numberNodes(root.right);
    }
    return count;
}
于 2011-08-02T07:10:41.090 に答える
1

プログラマーは、AVLツリーの概念を使用してバイナリツリーのバランスを取ります。とても簡単です。詳細については、オンラインで見つけることができます。クイックウィキリンク

以下は、AVLアルゴリズムを使用してツリーバランスをとるサンプルコードです。

Node *BinarySearchTree::leftRotation(Node *root)
{
    if(NULL == root)
    {
        return NULL;
    }
    Node *rightOfTheRoot = root->mRight;
    root->mRight = rightOfTheRoot->mLeft;
    rightOfTheRoot->mLeft = root;

    return rightOfTheRoot;
}

Node *BinarySearchTree::rightRotation(Node *root)
{
    if(NULL == root)
    {
        return NULL;
    }
    Node *leftOfTheRoot = root->mLeft;
    root->mLeft = leftOfTheRoot->mRight;
    leftOfTheRoot->mRight = root;

    return leftOfTheRoot;
}

Node *BinarySearchTree::doAVLBalance(Node *root)
{
    if(NULL == root)
    {
        return NULL;
    }
    else if(root->isBalanced())
    {
        return root;
    }

    root->mLeft  = doAVLBalance(root->mLeft);
    root->mRight = doAVLBalance(root->mRight);

    getDepth(root);

    if(root->isRightHeavy())
    {
        if(root->mRight->isLeftHeavy())
        {
            root->mRight = rightRotation(root->mRight);
        }
        root = leftRotation(root);
    }
    else if(root->isLeftHeavy())
    {
        if(root->mLeft->isRightHeavy())
        {
            root->mLeft = leftRotation(root->mLeft);
        }
        root = rightRotation(root);
    }

    return root;
}

クラス定義

class BinarySearchTree
{
public:
    // .. lots of methods 
    Node *getRoot();
    int getDepth(Node *root);

    bool isAVLBalanced();
    int calculateAndGetAVLBalanceFactor(Node *root);
    void doAVLBalance();

private:
     Node *mRoot;
};

class Node
{
public:
    int  mData;
    Node *mLeft;
    Node *mRight;
    bool mHasVisited;
    int mDepth;
public:

    Node(int data)
    : mData(data),
      mLeft(NULL),
      mRight(NULL),
      mHasVisited(false),
      mDepth(0)
    {
    }

    int getData()              { return mData; }

    void setData(int data)     { mData = data;  }

    void setRight(Node *right) { mRight = right;}

    void setLeft(Node *left)   { mLeft = left; }

    Node * getRight()          { return mRight; }

    Node * getLeft()           { return mLeft; }

    bool hasLeft()             { return (mLeft != NULL);  }

    bool hasRight()            { return (mRight != NULL); }

    bool isVisited()           { return (mHasVisited == true); }

    int getAVLBalanceFactor()
    {
        int leftTreeDepth = (mLeft != NULL) ? mLeft->mDepth : -1;
        int rightTreeDepth = (mRight != NULL) ? mRight->mDepth : -1;
        return(leftTreeDepth - rightTreeDepth);
    }

    bool isRightHeavy() { return (getAVLBalanceFactor() <= -2); }

    bool isLeftHeavy()  { return (getAVLBalanceFactor() >= 2);  }

    bool isBalanced()
    {
        int balanceFactor = getAVLBalanceFactor();
        return (balanceFactor >= -1 && balanceFactor <= 1);
    }
};
于 2011-08-02T16:45:33.917 に答える