StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
primarykey
Id
6915543
data
AcceptedAnswerId
0
AnswerCount
0
ClosedDate
CommentCount
2
CommunityOwnedDate
CreationDate
2011-08-02T16:45:33.917
FavoriteCount
0
LastActivityDate
2011-08-03T04:29:09.543
LastEditDate
2011-08-03T04:29:09.543
LastEditorUserId
842435
OwnerUserId
842435
ParentId
6907113
PostTypeId
2
Score
1
ViewCount
0
LastEditorDisplayName
text
Body
Programmers use AVL Tree concepts to balance binary trees. It is quite simple. More information can be found online. Quick wiki <a href="http://en.wikipedia.org/wiki/AVL_tree" rel="nofollow">link</a> Below is the sample code which does tree balance using AVL algorithm. <pre><code>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; } </code></pre> Class Definition <pre><code>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); } }; </code></pre>
Tags
Title
singulars
PostAcceptedAnswerId
1. This table or related slice is empty.
PostParentId
1. POBalancing String based Binary Search Tree (For Spellchecking)
 singulars
 PostTypePostTypeId
 PTQuestion
PostTypePostTypeId
1. PTAnswer
UserLastEditorUserId
1. USShash316
UserOwnerUserId
1. USShash316
plurals
PostLinksPostIdRelatedPostId
1. This table or related slice is empty.
PostLinksRelatedPostIdPostId
1. This table or related slice is empty.
PostsAcceptedAnswerId
1. POBalancing String based Binary Search Tree (For Spellchecking)
 singulars
 PostTypePostTypeId
 PTQuestion
PostsParentIdCreationDate
1. This table or related slice is empty.
VotesPostIdCreationDate
1. VO
 singulars
 PostPostId
 PO
 UserUserId
 This table or related slice is empty.
 VoteTypeVoteTypeId
 VTUpMod
2. VO
 singulars
 PostPostId
 PO
 UserUserId
 This table or related slice is empty.
 VoteTypeVoteTypeId
 VTAcceptedByOriginator
CommentsPostId
1. COthank you for that sample code!! Wrote my code according to that (Updated original post). Though I'm a little confused, why is it type "Node"? I tried that with mine ("TreeNode") but it wouldn't accept it...so I made it into an int. But now it doesn't want to accept the returns "Error: return value type does not match the function type". Besides that everything else is okay. I just don't know what type to write it as.
 singulars
 PostPostId
 PO
 UserUserId
 USRiotson
2. CONo matter how much I tried I couldn't get your sample code to work, I kept getting an "Incompatible" error, I tried changing things several times/doing it different ways, even my way, but I still cannot get the "Balancing" to work 100% :(. Updated my post...if you could help please, would be much appreciated!!
 singulars
 PostPostId
 PO
 UserUserId
 USRiotson

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.