河源市规划建设局网站,jquery特效网站,陕西汉中最新消息今天,企业网上商城因为上BST课的时候睡觉睡过了结果。。。#xff0c;后者折腾了一个下午才写了出来#xff0c;感谢http://blog.chinaunix.net/uid-24948645-id-3913917.html博客的详细解析#xff0c;但是上面的不足之处在于代码是伪代码#xff0c;基本实现不了#xff0c;然后自己做了修…因为上BST课的时候睡觉睡过了结果。。。后者折腾了一个下午才写了出来感谢http://blog.chinaunix.net/uid-24948645-id-3913917.html博客的详细解析但是上面的不足之处在于代码是伪代码基本实现不了然后自己做了修改改成c的写法。 AVL树平衡二叉树数据结构AVL树是最先发明的自平衡二叉查找算法是平衡二叉树的一种。在AVL中任何节点的两个儿子子树的高度最大差别为1所以它又被成为高度平衡树。查找、插入和删除在平均和最坏情况下都是O(log n)。增加和删除可能需要通过一次或多次树旋转来平衡这棵树。 假设把AVL树构造过程中需要重新平衡的节点叫做α。由于任意节点最多有两个儿子因此高度不平衡时α点的两颗子树的高度差2。这种不平衡可能出现在下面这四种情况 1 对α的左儿子的左子树进行一次插入右旋 其中D是新插入的节点红色节点K2是失去平衡的节点。需要对K1和K2进行左旋调整即将K1作为根将K2作为K1的左子树K1的右子树调整为K2的左子树。如下图所示 进行右旋变换 node* L_Ratate(node *K2) //左旋
{node *K1;K1 K2-Left;K2-Left K1-Right;K1-Right K2;//更新节点的高度return K1;
} 2对α的右儿子的右子树进行一次插入左旋 将K2的右子树更改为K1的左子树K1的左子树更改为K2即完成的右旋如下图所示 进行左旋 node* R_Ratate(node* K2)
{node* K1;K1 K2-Right;K2-Right K1-Left;K1-Left K2;//更新节点高度return K1;
}3对α的右儿子的左子树进行一次插入右左双旋 右左双旋先对K1和K2进行左旋然后在对K2和K3进行右旋最终实现平衡。如下图所示 进行一次右旋进行一次左旋
node* DoubleL_Rotate(node* K3)//双向旋转(左右)
{K3-Left R_Ratate(K3-Left);return L_Ratate(K3);
} 4对α的左儿子的右子树进行一次插入左右双旋 左右双旋这里的左右指的是对α的左儿子的右子树进行插入时需要旋转。先对K1和K2进行右旋跟第四种情况类似然后再对K3和K2进行左旋最终实现平衡。如下图所示 进行一次左旋进行一次右旋 node* DoubleR_Rotate(node* K3)//双向旋转(右左)
{K3-Right L_Ratate(K3-Right);return R_Ratate(K3);
}完整代码 #includeiostream
#includealgorithm
using namespace std;
typedef struct Node
{int data;int bf;//用来表示平衡因子struct Node *Left,*Right;
} node;
node* L_Ratate(node *K2) //左旋
{node *K1;K1 K2-Left;K2-Left K1-Right;K1-Right K2;//更新节点的高度return K1;
}
node* R_Ratate(node* K2)
{node* K1;K1 K2-Right;K2-Right K1-Left;K1-Left K2;//更新节点高度return K1;
}
node* DoubleL_Rotate(node* K3)//双向旋转(左右)
{K3-Left R_Ratate(K3-Left);return L_Ratate(K3);
}
node* DoubleR_Rotate(node* K3)//双向旋转(右左)
{K3-Right L_Ratate(K3-Right);return R_Ratate(K3);
}
int Height(node* P)
{if(P NULL)return -1; //当构建根节点或者是叶子节点的时候为-11正好为0elsereturn P-bf;
}node* create_bst(node* bst,int x)
{//coutok\n;if(!bst){//coutok\n;bstnew node;bst-datax;bst-bf0;bst-Leftbst-RightNULL;}else if(xbst-data){bst-Leftcreate_bst(bst-Left,x);if(Height(bst-Left)-Height(bst-Right)2)//左子树插入节点所以高度是左子树高于右子树{if(xbst-Left-data)//对α的左儿子的左子树进行一次插入需要左旋bstL_Ratate(bst);else//对α的左儿子的右子树进行一次插入需要双旋bstDoubleL_Rotate(bst);}}else if(xbst-data)//右子树插入新节点{bst-Right create_bst(bst-Right,x);if(Height(bst-Right) - Height(bst-Left) 2)//因为是右子树插入新节点所以高度是右子树高于左子树{if(x bst-Right-data)//对α的右儿子的右子树进行一次插入需要右旋bst R_Ratate(bst);else//对α的右儿子的左子树进行一次插入需要双旋bst DoubleR_Rotate(bst);}}bst-bf max(Height(bst-Left), Height(bst-Right)) 1;//couttestbst-bfendl;return bst;
}
void InOrder(node* bst)
{if(!bst)return;else{InOrder(bst-Left);coutbst-data endl;InOrder(bst-Right);}
}
int main()
{int n;cout请输入要构建的二叉平衡树序列长度endl;cinn;cout请输入要构建的二叉平衡树序列endl;node *bstNULL;for(int i0; in; i){int d;cind;bstcreate_bst(bst,d);}cout....输出....endl;InOrder(bst);return 0;
}
