紅黑樹插入操作分析及代碼實作

首先說一下紅黑樹的五個性質：

1、每個結點要麼是紅色的，要麼是黑色的； 2、根結點是黑色的； 3、每個葉結點，即空結點(NIL)是黑色的； 4、如果一個結點是紅色的，那麼它的兩個子結點都是黑色的； 5、對每個結點，從該結點到其子結點的所有路徑上包含相同數目的黑結點。

在對紅黑樹插入的時候，我們一般都會插入紅色的結點，紅黑樹的插入主要有這幾種情況：

1、插入的是根結點；

     此時，隻會違反性質2，那麼直接把此結點塗為黑色即可。

2、插入的結點的父節點是黑色的；

     此時什麼都不需要做。

3、插入的結點的父節點是紅色且叔父結點是紅色；

     此時又分為幾種情況：           1）、父節點是祖父結點的左子樹還是右子樹；                2）、插入的結點是父節點的左子樹還是右子樹。      無論哪種情況，解決政策都是：           對插入的結點（目前結點）的父節點和叔父結點塗黑，祖父結點塗紅，把目前結點指向祖父結點，遞歸執行第1種情況。

4、插入的結點的父節點是紅色，叔父結點是黑色的。

     這種情況又分為以下幾種情況：      1）、插入結點為父結點的左結點，父節點為祖父結點的左結點；           解決方案：父節點變黑，祖父結點變紅，然後以祖父結點為支點右旋。      2）、插入結點為父節點的右節點，父節點為祖父結點的左結點；           解決方案：以目前結點的父節點為支點左旋，然後再以目前結點的左結點執行第1）種情況。      3）、插入結點為父節點的左結點，父節點為祖父結點的右節點；           解決方案：以目前結點的父節點為支點右旋，然後再以目前結點的右節點執行第4）中情況。      4）、插入結點為父節點的右節點，父節點為祖父結點的右節點。           解決方案：父節點變黑，祖父結點變紅，然後以祖父結點為支點左旋。

代碼實作如下：

package com.tyxh.rab;

public class TreeNode {
     public int data;
     public TreeNode lchild;
     public TreeNode rchild;
     public TreeNode parent;
     public boolean color;
     public TreeNode( int data, TreeNode lchild, TreeNode rchild,
              TreeNode parent, boolean color) {
           this. data = data;
           this. lchild = lchild;
           this. rchild = rchild;
           this. parent = parent;
           this. color = color;
     }
     
}
           

package com.tyxh.rab;

public class BTTree {
     public static final boolean RED = false;
     public static final boolean BLACK = true;
     private TreeNode root;

     public BTTree() {
           root = null;
     }

     public TreeNode grandParentNode(TreeNode node) {
           // 獲得祖父節點
           return node. parent. parent;
     }

     public TreeNode uncleParentNode(TreeNode node) {
           // 獲得叔父節點
           if (node. parent == grandParentNode(node). lchild)
               return grandParentNode(node). rchild;
           else
               return grandParentNode(node). lchild;
     }

     // 左旋
     private void singRotateLeft(TreeNode k2) {
          TreeNode k1 = k2. rchild;
          k2. rchild = k1. lchild;
          k1. lchild = k2;
     }

     // 右旋
     private void singRotateRight(TreeNode k2) {
          TreeNode k1 = k2. lchild;
          k2. lchild = k1. rchild;
          k1. rchild = k2;
     }

     // 插入
     // 1、新結點位于樹的根上，沒有父節點
     public void insert_case1(TreeNode node) {
           if (node. parent == null)
              node. color = BLACK;
           else
              insert_case2(node);
     }

     // 2、新節點的父節點是黑色的
     public void insert_case2(TreeNode node) {
           if (node. parent. color == BLACK)
               return;
           else
              insert_case3(node);
     }

     // 3、父節點是紅色的，叔父節點也是紅色的
     public void insert_case3(TreeNode node) {
           if (uncleParentNode(node) != null && uncleParentNode(node).color == RED ) {
              node. parent. color = BLACK;
              uncleParentNode(node). color = BLACK;
              grandParentNode(node). color = RED;
              insert_case1(grandParentNode(node));
          } else
              insert_case4(node);
     }

     // 4、父節點是紅色的，叔父結點是黑色的或者為Nil，并且插入結點是父節點的右節點，父節點是祖父結點的左結點
     public void insert_case4(TreeNode node) {
           if (node == node. parent. rchild
                   && node. parent == grandParentNode(node).lchild) {
               // 以node.parent為結點左旋
              singRotateLeft(node. parent);
              node = node. lchild;
          } else if (node == node. parent. lchild
                   && node. parent == grandParentNode(node).rchild) {
               // 以node.parent為結點右旋
              singRotateRight(node. parent);
              node = node. rchild;
          }
          insert_case5(node);
     }

     // 5、父親結點是紅色的，叔父是黑色的或者為Nil，并且插入結點是父節點的左結點，父節點是祖父結點的左結點
     public void insert_case5(TreeNode node) {
          node. parent. color = BLACK;
          grandParentNode(node). color = RED;
           if (node == node. parent. lchild
                   && node. parent == grandParentNode(node).lchild) {
               // 以祖父結點為結點右旋
              singRotateRight(grandParentNode(node));
          } else if (node == node. parent. rchild
                   && node. parent == grandParentNode(node).rchild) {
               // 以祖父結點為結點左旋
              singRotateLeft(grandParentNode(node));
          }

     }

     // 中序周遊
     public void traversal() {
          insubtree( root);
     }

     private void insubtree(TreeNode node) {
           if (node == null)
               return;
          insubtree(node. lchild);
          System. out.println(node. data + "、");
          insubtree(node. rchild);
     }
}