Бинарное дерево поиска на основе балансировки строк (для проверки орфографии)

Question

Обновление: я не могу заставить "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
};

Answer 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);
    }
};

Answer 2

К сожалению, мы, программисты, буквальные звери.

сделать это "Сбалансированным" деревом.

"Сбалансированный" зависит от контекста. Классы структур вводных данных обычно ссылаются на то, что дерево "сбалансировано", когда разница между узлом наибольшей глубины и узлом наименьшей глубины сведена к минимуму. Однако, как упомянул сэр Templatetypedef, Splay Tree считается балансирующим деревом. Это связано с тем, что он может довольно хорошо сбалансировать деревья в тех случаях, когда к нескольким узлам часто обращаются одновременно. Это связано с тем, что в этих случаях требуется меньше обходов узлов для получения данных в дереве отображения, чем в обычном двоичном дереве. С другой стороны, его наихудшая производительность при доступе к доступу может быть такой же плохой, как и у связанного списка.

Говоря о связанных списках...

Потому что в противном случае без "Балансировки" это то же самое, что и связанный список, который я читаю, и он побеждает цель.

Это может быть так же плохо, но для рандомизированных вставок это не так. Если вы вставите уже отсортированные данные, большинство реализаций бинарного дерева поиска будут хранить данные в виде раздутого и упорядоченного связанного списка. Однако это только потому, что вы постоянно строите одну сторону дерева. (Представьте, что вы вставляете 1, 2, 3, 4, 5, 6, 7 и т. Д. В двоичное дерево. Попробуйте на бумаге и посмотрите, что получится.)

Если вам нужно балансировать в теоретическом смысле, который должен быть гарантирован, то я рекомендую посмотреть на красно-черные деревья. (Google, вторая ссылка довольно хорошая.)

Если вам нужно сбалансировать его разумным образом для этого конкретного сценария, я бы использовал целочисленные индексы и достойную хеш-функцию - таким образом, балансировка будет происходить вероятностно без какого-либо дополнительного кода. То есть, сделайте вашу функцию сравнения похожей на хэш (strA)

Если вам это сойдет с рук, я настоятельно рекомендую последнее, если вам не хватает времени и вы хотите чего-то быстрого. В противном случае, красно-черные деревья являются полезными, поскольку они чрезвычайно полезны на практике, когда вам нужно свернуть свои собственные двоичные деревья с сбалансированной высотой.

Наконец, обращаясь к вашему коду выше, смотрите комментарии в коде ниже:

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;
}

Answer 3

Есть много способов сделать это, но я бы посоветовал вам не делать этого как все. Если вы хотите хранить BST строк, есть гораздо лучшие варианты:

1. Используйте предварительно написанный класс бинарного дерева поиска. Класс C++ std::set предлагает те же гарантии времени, что и сбалансированное двоичное дерево поиска, и часто реализуется как таковой. Это существенно проще в использовании, чем прокатка собственного BST.

2. Вместо этого используйте Trie. Трехуровневая структура данных проще и эффективнее, чем BST строк, не требует никакой балансировки и работает быстрее, чем BST.

Если вы действительно должны написать свой собственный сбалансированный BST, у вас есть много вариантов. Большинство реализаций BST, которые используют балансировку, чрезвычайно сложны и не для слабонервных. Я бы предложил реализовать либо Treap, либо Splay Tree, которые представляют собой две сбалансированные структуры BST, которые довольно просты в реализации. Они оба более сложны, чем код, который у вас есть выше, и я не могу в этом кратком изложении представить реализацию, но поиск по этим структурам в Википедии должен дать вам много советов о том, как действовать дальше.

Надеюсь это поможет!