首页 > 代码库 > 红黑树的旋转（C语言）
红黑树的旋转（C语言）
1.红黑树为什么要执行旋转操作
原因：红黑树在执行Insert和Delete对二叉搜索树进行操作时，结果可能会违反红黑树的性质，需要改变树中某些结点的颜色和指针结构。
指针结构的修改：通过左旋、右旋来改变的。
特点：旋转操作保持二叉搜索树性质的局部性操作。
2.算法代码
1 //左旋 2 static void rbTreeLeftRotate(RBTree *rbTree, RBTreeNode *x) 3 { 4 RBTreeNode *y; 5 6 y = x->right; //设置一个指针型变量来存放x右孩子的地址， 7 x->right = y->left; //此处将x的右孩子替换成y的左孩子 8 9 if (y->left !=NULL)10 y->left->parent = x;11 12 y->parent = x->parent;13 14 if (x->parent == NULL)15 *rbTree = y;16 else 17 {18 if (x->parent->left == x)19 x->parent->left = y;20 else21 x->parent->right = y; 22 }23 y->left = x;24 x->parent = y;25 }
1 //右旋 2 static void rbTreeRightRotate(RBTree *rbTree, RBTreeNode *x) 3 { 4 RBTreeNode *y; 5 6 y = x->left; 7 x->left = y->right; 8 9 if (y->right !=NULL)10 y->right->parent = x; //link y->right to x->left11 12 y->parent = x->parent ; 13 if (x->parent == NULL) //link x->parent to y14 *rbTree = y;15 else16 {17 if (x->parent->left = x)18 x->parent->left = y;19 else20 x->parent->right = y;21 }22 y->right = x;23 x->parent = y;24 25 }
红黑树的旋转（C语言）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。