紅黑樹是一種二叉平衡查找樹，每個結點上有一個存儲位來表示結點的顏色，可以是RED或BLACK。
紅黑樹具有以下性質：
(1) 每個結點是紅色或是黑色
(2) 根結點是黑色的
(3) 如果一個結點是紅色的，則它的兩個兒子都是黑色的
(4) 對於每個結點，從該結點到其子孫結點的所有路徑上包含相同數目的黑結點
通過紅黑樹的性質，可以保證所有基於紅黑樹的實現都能保證操作的運行時間為對數級別（範圍查找除外。它所需的額外時間和返回的鍵的數量成正比）。
Java的TreeMap就是通過紅黑樹實現的。
紅黑樹的操作如果不畫圖很容易搞糊塗，下面通過圖示來說明紅黑樹的插入操作。
插入一個紅色的節點到紅黑樹中之後，會有6種情況：圖示中N表示插入的節點，P表示父節點，U表示叔叔節點，G表示祖父節點，X表示當前操作節點
代碼如下：
public class RedBlackBST<Key extends Comparable<Key>, Value> { private Node root; private static final boolean RED = true; private static final boolean BLACK = false; private class Node{ private Key key; //鍵private Value val; //值private Node left, right, parent; //左右子樹和父節點private boolean color; //由其父節點指向它的鏈接的顏色public Node(Key key, Value val,Node parent, boolean color){ this.key = key; this.val = val; this.color = color; } } public Value get(Key key){ Node x = root; while(x!=null){ int cmp = key.compareTo(x.key); if(cmp < 0 ) x = x.left; else if(cmp > 0) x = x.right; else return x.val; } return null; } public void put(Key key, Value val){ if(root==null) { //如果是根節點，就將節點新建為黑色root = new Node(key,val,null,BLACK); return; } //尋找合適的插入位置Node parent = null; Node cur = root; while(cur!=null) { parent = cur; if(key.compareTo(cur.key)>0) cur=cur.right; else cur = cur.left; } Node n = new Node(key,val,parent,RED); //普通的新建節點為紅色//將新節點插入parent下if(key.compareTo(parent.key) > 0) parent.right = n; else parent.left = n; //插入新節點後要調整樹中部分節點的顏色和屬性來保證紅黑樹的特徵不被破壞fixAfterInsertion(n); } private Node parentOf(Node x) { return (x==null ? null : x.parent); } private boolean colorOf(Node x) { return (x==null ? BLACK : x.color); } private Node leftOf(Node x) { return (x==null ? null : x.left); } private Node rightOf(Node x) { return(x==null ? null : x.right); } private void setColor(Node x, boolean color) { if(x!=null) x.color = color; } private void fixAfterInsertion(Node x) { while(x!=null && colorOf(parentOf(x)) == RED) { Node grandPa = parentOf(parentOf(x)); Node parent = parentOf(x); if(parent == leftOf(grandPa)) {//case 1 || case2 || case3 Node uncle = rightOf(grandPa); if(colorOf(uncle) == RED) {//case1, uncle is red setColor(parent,BLACK); //父節點置黑setColor(uncle, BLACK); //叔叔節點置黑setColor(grandPa,RED); //祖父節點置紅x = grandPa; //因為祖父節點由黑轉紅，故要重新調整父節點及其祖先的紅黑屬性}else {//case2 || case3,uncle is black if(x==rightOf(parent)) { //case2 x = parent; rotateLeft(x); } //case3 setColor(parent,BLACK); setColor(grandPa, RED); rotateRight(grandPa); } }else {//case4 || case 5 || case6 Node uncle = leftOf(grandPa); if(colorOf(uncle) == RED) { //case4 || case5 || case6 setColor(parent,BLACK); setColor(uncle, BLACK); setColor(grandPa,RED); x = grandPa; }else{ //case5 || case6, uncle is black if(x==leftOf(parent)) { //case5 x = parent; rotateRight(x); } //case6 setColor(parent,BLACK); setColor(grandPa, RED); rotateLeft(grandPa); } } } } private void rotateLeft(Node x) { if(x==null) return; Node y = x.right; x.right = y.left; if(y.left!=null) y.left.parent = x; y.left = x; y.parent = x.parent; if(x.parent == null) { root = y; } else if(x.parent.left == x) { x.parent.left = y; }else { x.parent.right = y; } x.parent = y; } private void rotateRight(Node x) { if(x==null) return; Node y = x.left; x.left = y.right; if(y.right != null) y.right.parent = x; y.right = x; y.parent = x.parent; if(x.parent == null) { root = y; }else if(x.parent.left==x) { x.parent.left = y; }else { x.parent.right=y; } x.parent = y; } }上面的rotateLeft和rotateRight有必要畫個圖示：
以上這篇基於紅黑樹插入操作原理及java實現方法(分享)就是小編分享給大家的全部內容了，希望能給大家一個參考，也希望大家多多支持武林網。