1

更新：我无法让“平衡”工作，因为我无法让“doAVLBalance”识别成员函数“isBalanced()”、“isRightHeavy()”、“isLeftHeavy”。而且我不知道为什么！我完全尝试了 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. 改用 trie。trie 数据结构比字符串的 BST 更简单、更有效，根本不需要平衡，并且比 BST 更快。

如果您真的必须编写自己的平衡 BST，那么您有很多选择。大多数使用平衡的 BST 实现都非常复杂，不适合胆小的人。我建议实现一个treap 或一个splay 树，这是两个平衡的BST 结构，实现起来相当简单。它们都比您上面的代码更复杂，我无法在这么短的篇幅中提供实现，但是在 Wikipedia 上搜索这些结构应该会为您提供大量关于如何进行的建议。

希望这可以帮助！

于 2011-08-02T05:21:44.060 回答
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 回答
1

不幸的是，我们程序员是真正的野兽。

使其成为“平衡”树。

“平衡”取决于上下文。介绍性数据结构类通常指的是当深度最大的节点和深度最小的节点之间的差异最小时，树是“平衡的”。然而，正如 Templatetypedef 爵士所提到的，展开树被认为是平衡树。这是因为它可以很好地平衡树，在少数节点同时访问频繁的情况下。这是因为在这些情况下，与传统的二叉树相比，在展开树中获取数据所需的节点遍历更少。另一方面，它在逐次访问的最坏情况下的性能可能与链表一样糟糕。

说到链表...

因为否则如果没有“平衡”，它与我阅读的链接列表相同并且违背了目的。

它可能同样糟糕，但对于随机插入却不是这样。如果您插入已排序的数据，大多数二叉搜索树实现将存储数据，如膨胀且有序的链表。然而，这只是因为你不断地构建树的一侧。（想象一下将 1、2、3、4、5、6、7 等...插入二叉树。在纸上尝试一下，看看会发生什么。）

如果您必须在理论上必须保证的最坏情况下进行平衡，我建议您查找红黑树。（谷歌一下，第二个链接很好。）

如果您必须在这种特定情况下以合理的方式平衡它，我会使用整数索引和一个不错的散列函数——这样平衡将在概率上发生，而无需任何额外的代码。也就是说，让你的比较函数看起来像 hash(strA) < hash(strB) 而不是你现在得到的。（对于这种情况的快速但有效的散列，查找 FNV 散列。首先点击谷歌。向下直到你看到有用的代码。）如果你愿意，你可以担心实现效率的细节。（例如，您不必在每次比较时都执行两个哈希，因为其中一个字符串永远不会改变。）

如果你能侥幸逃脱，我强烈推荐后者，如果你时间紧迫并且想要快速的东西。否则，红黑树是值得的，因为当您需要滚动自己的高度平衡二叉树时，它们在实践中非常有用。

最后，解决上面的代码，请参阅下面代码中的注释：

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 回答