平衡基于字符串的二叉搜索树(用于拼写检查)

Update:我不能让"Balancing"工作，因为我不能让"doAVLBalance"识别成员函数"isBalanced()"， "isRightHeavy()"， "isLeftHeavy"。我不知道为什么!我试过Sash的例子(第三个答案)，但我得到"减速是不兼容的"，我无法解决这个问题…所以我试着用我的方式…它告诉我那些成员函数不存在，而它们显然是存在的。

"错误:类"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
};

程序员使用AVL树的概念来平衡二叉树。这很简单。更多信息可以在网上找到。快速wiki链接

下面是使用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);
    }
};

有很多方法可以做到这一点，但我建议您不要全部这样做。如果要存储字符串的BST，有更好的选择:

使用预先编写的二叉搜索树类。c++ std::set类提供了与平衡二叉搜索树相同的时间保证，并且通常是这样实现的。这比滚动你自己的BST要容易得多。
使用tree代替。trie数据结构比字符串的BST更简单，更有效，根本不需要平衡，并且比BST更快。

如果你真的必须编写自己的平衡BST，你有很多选择。大多数使用平衡的BST实现都非常复杂，不适合胆小的人。我建议实现treap或展树，这是两种平衡的BST结构，实现起来相当简单。它们都比你上面的代码更复杂，我无法在这里提供一个实现，但是在维基百科上搜索这些结构应该会给你很多关于如何继续的建议。

希望这对你有帮助!

不幸的是，我们程序员都是文字怪兽。

使它成为"平衡"树。

"Balanced"是上下文相关的。介绍性数据结构类通常指的是当最大深度节点和最小深度节点之间的差值最小时，树是"平衡的"。然而，正如Sir 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;
}

相关内容

最新更新

热门标签：