怎么构建平衡二叉树（AVL树）

2013-10-21

如何构建平衡二叉树（AVL树）一、基本概念：平衡二叉树（Balanced Binary Tree）又被称为AVL树（有别于AVL算法），

如何构建平衡二叉树（AVL树）

一、基本概念：

平衡二叉树（Balanced Binary Tree）又被称为AVL树（有别于AVL算法），且具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。

二、四种旋转情况

当我们对AVL树进行删除或者插入操作时，有可能会导致其左右子树高度差不超过1的性质遭到破坏，因此需要进行旋转操作来调整。

旋转操作分为以下四种情况：

（1）左左（2）左右（3）右左（4）右右

怎么构建平衡二叉树（AVL树）

对于“左左”和“右右”的情况，只要进行一次单旋转就可以使其恢复平衡。如下图：

怎么构建平衡二叉树（AVL树）

相应的给出代码：


相应的代码：
 int getHeight(TreeNode *t) {    if(t == NULL) return -1;    else return t->height; } bool isBalanced(TreeNode *left,TreeNode *right) { return abs(getHeight(left) - getHeight(right)) < 2; } TreeNode* insert(int v, TreeNode *root) {if(root == NULL){root = new TreeNode(v);return root;}if(v > root->value) //节点插入在右子树中{root->right = insert(v,root->right);if(!isBalanced(root->left,root->right)){if(v > root->right->value)root = SingleRotateRight(root);elseroot = DoubleRotateRL(root);}}else{root->left = insert(v,root->left);if(!isBalanced(root->left,root->right)){if(v < root->left->value)root = SingleRotateLeft(root);elseroot = DoubleRotateLR(root);}}root->height = max(getHeight(root->left),getHeight(root->right)) + 1;return root; }

四、删除操作
五、查找操作  
六、参考资料
http://www.cppblog.com/cxiaojia/archive/2013/07/22/187776.html

热点排行

编程

怎么构建平衡二叉树（AVL树）