红黑树的旋转操作

作者：追风剑情发布于：2017-8-19 23:03 分类：Algorithms
参考 http://blog.csdn.net/xudong_98/article/details/51471688
左旋转与右旋转互为逆操作
示例：C#
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace RedBlackTree1
{
    class Program
    {
        static void Main(string[] args)
        {
            int[] keys = new int[] { 13, 8, 1, 11, 6, 17, 15, 25, 22, 27};
            Console.Write("测试数据为: ");
            for (int i = 0; i < keys.Length; i++)
            {
                Console.Write(keys[i] + " ");
            }
            Console.WriteLine();

            //根节点
            Node root = null;
            //录入10个节点
            for (int i = 0; i < keys.Length; i++)
            {
                Node node = new Node();
                node.key = keys[i];
                if (null == root)
                    root = node;
                else
                    Insert(root, node);
            }
            Console.Write("构建的二叉搜索树为: ");
            Print(root);

            Console.WriteLine();
            Console.WriteLine("给二叉搜索树染色: ");
            Coloring(root, Color.Black);//根节点为黑色
            Print(root, true);

            Console.WriteLine();

            Console.WriteLine("对key等于8的结点进行右旋转");
            Node node8 = GetNodeByKey(root, 8);
            RotationRight(node8);
            Print(root, true);

            Console.WriteLine();

            Console.WriteLine("对key等于1的结点进行左旋转");
            Node node1 = GetNodeByKey(root, 1);
            RotationLeft(node1);
            Print(root, true);

            Console.ReadKey();
        }

        static Node GetNodeByKey(Node node, int key)
        {
            if (node == null)
                return null;
            if (node.key == key)
                return node;

            Node left = GetNodeByKey(node.left, key);
            if (left != null && left.key == key)
                return left;

            Node right = GetNodeByKey(node.right, key);
            if (right != null && right.key == key)
                return right;

            return null;
        }

        static void Insert(Node root, Node child)
        {
            if(root.key >= child.key)
            {
                if (null == root.left)
                {
                    root.left = child;
                    child.parent = root;
                    
                }
                else
                {
                    Insert(root.left, child);
                }
            }
            else
            {
                if (null == root.right)
                {
                    root.right = child;
                    child.parent = root;
                }
                else
                {
                    Insert(root.right, child);
                }
            }
        }

        // 向左旋转
        static void RotationLeft(Node node)
        {
            //必须要有右节点
            if (node.right == null)
                return;

            //轴节点
            Node pivot = node;
            //轴的左节点
            Node left = node.left;
            //轴的右节点
            Node right = node.right;
            //轴的右节点的左节点
            Node right_left = right.left;

            //改变轴的父节点相应指针的指向
            Node pivot_parent = pivot.parent;
            if (null != pivot_parent)
            {
                if (pivot_parent.left == pivot)
                {
                    pivot_parent.left = right;

                }
                else if (pivot_parent.right == pivot)
                {
                    pivot_parent.right = right;
                }
            }
            //右节点的父指针指向轴节点的父
            right.parent = pivot_parent;
            //右节点的左指针指向轴节点
            right.left = pivot;
            //轴节点的父指针指向右节点
            pivot.parent = right;
            //轴节点的右指针指向右节点的左节点
            pivot.right = right_left;
            if (null != right_left)
                right_left.parent = pivot;
        }

        // 向右旋转
        static void RotationRight(Node node)
        {
            //必须要有左节点
            if (node.left == null)
                return;

            //轴节点
            Node pivot = node;
            //轴的左节点
            Node left = node.left;
            //轴的右节点
            Node right = node.right;
            //轴的左节点的右节点
            Node left_right = left.right;

            //改变轴的父节点相应指针的指向
            Node pivot_parent = pivot.parent;
            if (null != pivot_parent)
            {
                if (pivot_parent.left == pivot)
                {
                    pivot_parent.left = left;
                    
                }
                else if (pivot_parent.right == pivot)
                {
                    pivot_parent.right = left;
                }
            }
            //左节点的父指针指向轴节点的父
            left.parent = pivot_parent;
            //左节点的右指针指向轴节点
            left.right = pivot;
            //轴节点的父指针指向左节点
            pivot.parent = left;
            //轴节点的左指针指向左节点的右节点
            pivot.left = left_right;
            if (null != left_right)
                left_right.parent = pivot;
        }

        static void Coloring(Node root, Color color)
        {
            if (null == root)
                return;
            root.color = color;
            color = (color == Color.Black) ? Color.Red : Color.Black;
            Coloring(root.left, color);
            Coloring(root.right, color);
        }

        static void Print(Node root, bool outputColor = false)
        {
            if (null == root)
                return;

            if (root != null)
            {
                if (outputColor)
                    Console.Write("{0}({1}) ", root.key, root.color);
                else
                    Console.Write("{0}  ", root.key);
            }

            Print(root.left, outputColor);
            Print(root.right, outputColor);
        }
    }

    public enum Color
    {
        Black,
        Red
    }

    public class Node
    {
        public Color color;
        public int key;
        public Node parent;
        public Node left;
        public Node right;
    }


}