平衡二叉树AVL中的左右旋转

在进行平衡二叉树的构建构成中,每当发现不平衡的结点就要及时的做平衡。根据不同的情况对最小不平衡子树进行左右旋转操作。例如:(左旋转)

blob.png

右边多的进行左旋转,把1拉下来,看起来想往左边转吧!

//左旋转
static void L_Rotate(ref Node node)//传入的是1
{
    Node temp;
    temp = node.cRight;
    node.cRight = temp.cLeft;//2的左结点设为给1的右节点
    temp.cLeft = node;//2的左边设为1
    node = temp;//原1的位置改为2,这解释,啧啧
}

node.cRight = temp.cLeft;-》如果说原来2是有左结点的话设为x,x<2,又2是1的右结点,所有1<x,又1的原右结点被破坏了,所以可以用1的右节点来承接x结点。如果不这样做的话,你试试,2有左右结点,然后一转,嘿嘿,三个结点了真是奇怪。


//右旋转
static void R_Rotate(ref Node node)
{
    Node temp;
    temp = node.cLeft;
    node.cLeft = temp.cRight;//原前驱,变左结点
    temp.cRight = node;
    node = temp;
}

右旋转和左旋转差不多,不同的是操作左右结点的不同。


首页 我的博客
粤ICP备17103704号