StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

POBalancing String based Binary Search Tree (For Spellchecking)
primarykey
Id
6907113
data
AcceptedAnswerId
6915543
AnswerCount
3
ClosedDate
CommentCount
0
CommunityOwnedDate
CreationDate
2011-08-02T04:00:15.853
FavoriteCount
0
LastActivityDate
2011-08-04T05:04:57.107
LastEditDate
2011-08-04T05:04:57.107
LastEditorUserId
732071
OwnerUserId
732071
ParentId
0
PostTypeId
1
Score
1
ViewCount
851
LastEditorDisplayName
text
Body
Update: I can't get "Balancing" to work, because I cannot get "doAVLBalance" to recognize the member functions "isBalanced()", "isRightHeavy()", "isLeftHeavy". And I don't know why! I tried Sash's example(3rd answer) exactly but I get "deceleration is incompatible" and I couldn't fix that...so I tried doing it my way...and it tells me those member functions don't exist, when they clearly do. "Error: class "IntBinaryTree:TreeNode" has no member "isRightHeavy". I'm stuck after trying for the last 4 hours :(. Updated code below, help would be much appreciated!! I'm creating a String based Binary Search Tree and need to make it a "Balanced" tree. How do I do this?* Help please!! Thanks in advance! BinarySearchTree.cpp: <pre><code> 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. </code></pre> BinarySearchTree.h: <pre><code>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 }; </code></pre>
Tags
<class><data-structures><spell-checking><binary-search-tree><tree-balancing>
Title
Balancing String based Binary Search Tree (For Spellchecking)
singulars
PostAcceptedAnswerId
1. PO
 singulars
 PostTypePostTypeId
 PTAnswer
PostParentId
1. This table or related slice is empty.
PostTypePostTypeId
1. PTQuestion
UserLastEditorUserId
1. USRiotson
UserOwnerUserId
1. USRiotson
plurals
PostLinksPostIdRelatedPostId
1. This table or related slice is empty.
PostLinksRelatedPostIdPostId
1. This table or related slice is empty.
PostsAcceptedAnswerId
1. This table or related slice is empty.
PostsParentIdCreationDate
1. PO
 singulars
 PostTypePostTypeId
 PTAnswer
2. PO
 singulars
 PostTypePostTypeId
 PTAnswer
3. PO
 singulars
 PostTypePostTypeId
 PTAnswer
VotesPostIdCreationDate
1. VO
 singulars
 PostPostId
 POBalancing String based Binary Search Tree (For Spellchecking)
 UserUserId
 This table or related slice is empty.
 VoteTypeVoteTypeId
 VTUpMod
CommentsPostId
1. This table or related slice is empty.

Querying!

Guidance

A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.