文章目錄

• 代碼實現(xiàn)
• • 節(jié)點實現(xiàn)類
  • 紅黑樹實現(xiàn)
• 單元測試

代碼實現(xiàn)

節(jié)點實現(xiàn)類

package csdn.dreamzuora.tree;/*** Title:* Description:** @version 1.0* @author: weijie* @date: 2020/10/19 13:30*/ public interface Node { } package csdn.dreamzuora.tree;import java.io.Serializable;/*** Title:* Description:** @version 1.0* @author: weijie* @date: 2020/10/19 13:27*/ public abstract class AbstractNode<T, E> implements Node, Serializable {private static final long serialVersionUID = -2321782309212147194L;/*** 數(shù)據(jù)域*/T data;/*** 左孩子*/E left;/*** 右孩子*/E right;public AbstractNode() {}public AbstractNode(T data) {this.data = data;}public T getData() {return data;}public void setData(T data) {this.data = data;}public E getLeft() {return left;}public void setLeft(E left) {this.left = left;}public E getRight() {return right;}public void setRight(E right) {this.right = right;} } package csdn.dreamzuora.tree;/*** Title: 紅黑樹節(jié)點* Description:** @version 1.0* @author: weijie* @date: 2020/10/21 14:36*/ public class RedBlackNode extends AbstractNode<Integer, RedBlackNode> {/*** 紅黑樹節(jié)點顏色標記*/boolean isBlack;/*** 紅黑樹父親節(jié)點*/RedBlackNode parent;public RedBlackNode(Integer data) {super(data);//默認為紅色this.isBlack = false;}public boolean isBlack() {return isBlack;}public void setBlack(boolean black) {isBlack = black;}public RedBlackNode getParent() {return parent;}public void setParent(RedBlackNode parent) {this.parent = parent;}@Overridepublic String toString() {return "RedBlackNode{" +"isBlack=" + isBlack +", data=" + data +'}';} }

紅黑樹實現(xiàn)

package csdn.dreamzuora.tree;import java.util.List;/*** Title: 樹接口* Description:** @version 1.0* @author: weijie* @date: 2020/10/16 14:56*/ public interface Tree<T,E> {/*** 構建樹* @param dataList*/void createTree(List<T> dataList);/*** 添加節(jié)點* @param data*/E addNode(E tree, T data);/*** 刪除節(jié)點* @param tree* @param node*/void deleteNode(E tree, E node);/*** 前序遍歷:根節(jié)點->左節(jié)點->右節(jié)點*/void preOrder(List<T> list, E node);/*** 中序遍歷：左節(jié)點->根節(jié)點->右節(jié)點* @return*/void inOrder(List<T> list, E node);/*** 后序遍歷：左節(jié)點->右節(jié)點->根節(jié)點*/void laOrder(List<T> list, E node);/*** 廣度優(yōu)先遍歷：層序遍歷* @param list* @param node*/void bfs(List<T> list, E node);} package csdn.dreamzuora.tree;import java.io.Serializable; import java.util.List;/*** Title: 二叉樹抽象類* Description:** @version 1.0* @author: weijie* @date: 2020/10/16 14:57*/ public abstract class AbstractTree<T, E> implements Tree<T, E>, Serializable {private static final long serialVersionUID = -8046156919125106629L;/*** 根節(jié)點*/E root;@Overridepublic void createTree(List<T> dataList) {for (T data : dataList){addNode(root, data);}}void addNode(T data){};} package csdn.dreamzuora.tree;import java.util.LinkedList; import java.util.List;/*** Title: 紅黑樹* Description:* 規(guī)則：* 1.每個節(jié)點不是紅色就是黑色* 2.每個根節(jié)點是黑色* 3.每個葉子節(jié)點就是黑色的空節(jié)點* 4.如果一個節(jié)點是紅色的，則它的子節(jié)點必須是黑色的(父子不能同為紅)* 5.平衡的關鍵字：從任一節(jié)點到其每個葉子的所有路徑都包含相同的黑色的節(jié)點* 6.新插入節(jié)點默認為紅色，插入后需要校驗紅黑樹是否符合規(guī)則，不符合則需要進行平衡** 再平衡涉及到：左旋、右旋、顏色反轉** 紅黑樹插入分為五種情況：** 1.新節(jié)點(A)位于樹根，沒有父節(jié)點* 直接讓新節(jié)點變成黑色，規(guī)則二得到滿足，同時，黑色的根節(jié)點使得每條路徑上的黑色節(jié)點數(shù)目都增加1，所以* 并沒有打破規(guī)則5* A(紅) -> A(黑)* 1 2 1 2*** 2.新節(jié)點(B)的父節(jié)點是黑色* 新插入的紅色結點B并沒有打破紅黑樹的規(guī)則，所以不需要做任何調整* A(黑)* B(紅) 3* 1 2*** 3.新節(jié)點(D)的父節(jié)點和叔叔節(jié)點都是紅色* A(黑) A(黑) A(紅)* B(紅) C(紅) -> B(黑) C(紅) -> ... ->B(黑) c(黑)* D(紅) 3 4 5 D(紅) D(紅)* 1 2*經過上面的調整，這一局部重新符合了紅黑樹的規(guī)則* 4.新節(jié)點(D)的父節(jié)點是紅色，叔叔節(jié)點是黑色或者沒有叔叔，且新節(jié)點是父節(jié)點的右孩子，父節(jié)點(B)是祖父節(jié)點的左孩子* 我們以節(jié)點B為軸，做一次左旋，使得節(jié)點D成為父節(jié)點，原來的父節(jié)點B成為D的左孩子* A(黑) A(黑)* B(紅) C(黑) -> D(紅) C(黑)* 1 D(紅) 4 5 B(紅) 3 4 5* 2 3 1 2** 5.新節(jié)點(D)的父節(jié)點是紅色，叔叔節(jié)點是黑色或者沒有叔叔，且新節(jié)點是父節(jié)點的左孩子，父節(jié)點（B）* 是祖父節(jié)點的左孩子* 我們以節(jié)點A為抽，做一次右旋轉，使得節(jié)點B成為祖父節(jié)點，節(jié)點A成為節(jié)點B的右孩子* A(黑) B(紅) B(黑)* B(紅) C(黑) -> D(紅) A(黑) -> D(紅) A(紅)* D 3 4 5 1 2 3 C(黑) 1 2 3 C(黑)* 1 2 4 5 4 5** 顏色反轉：* 如果當前節(jié)點、父節(jié)點、叔叔節(jié)點同為紅色，這種情況違反了紅黑樹的規(guī)則，需求將紅色向祖輩上傳，* 父節(jié)點和叔叔節(jié)點變?yōu)楹谏?#xff0c;爺爺節(jié)點變?yōu)楹?>紅色** 左旋：逆時針旋轉紅黑樹的兩個節(jié)點，使得父節(jié)點被自己的右孩子取代，而自己成為自己的左孩子*** 右旋：順時針旋轉紅黑樹的兩個節(jié)點，使得父節(jié)點被自己的左孩子取代，而自己成為自己的右孩子** 時間負責度：logn* @version 1.0* @author: weijie* @date: 2020/10/19 17:39*/ public class RedBlackTree extends AbstractTree<Integer, RedBlackNode> {@Overridepublic void createTree(List<Integer> dataList) {for (Integer data : dataList){addNode(data);}}@Overridepublic void addNode(Integer data) {RedBlackNode node = new RedBlackNode(data);if (root == null){//根為黑色node.setBlack(true);root = node;return ;}RedBlackNode parent = root;RedBlackNode son = null;/*** 判斷新節(jié)點是放在左子樹還是右子樹*/if (data <= parent.getData()){son = parent.getLeft();}else {son = parent.getRight();}/*** 對樹深度遍歷，尋找新節(jié)點存放的位置*/while (son != null){parent = son;if (data <= parent.getData()){son = parent.getLeft();}else {son = parent.getRight();}}/*** 節(jié)點插入*/if (data <= parent.getData()){parent.setLeft(node);}else {parent.setRight(node);}node.setParent(parent);/*** 自平衡*/balance(node);}@Overridepublic RedBlackNode addNode(RedBlackNode tree, Integer data) {return null;}/*** 自平衡* @param node*/private void balance(RedBlackNode node){RedBlackNode father;RedBlackNode grandFather;/*** 獲取父節(jié)點并判斷父節(jié)點是否為紅色節(jié)點，規(guī)則：父子不同為紅*/while ((father = node.getParent()) != null && father.isBlack() == false){//獲取祖父節(jié)點grandFather = father.getParent();//判斷父節(jié)點在祖先節(jié)點存在的位置if (grandFather.getLeft() == father){//叔叔節(jié)點RedBlackNode uncle = grandFather.getRight();//如果父親、叔叔節(jié)點存在且都為紅，則父親、叔叔節(jié)點變?yōu)楹谏?/span>if (uncle != null && uncle.isBlack() == false){father.setBlack(true);uncle.setBlack(true);grandFather.setBlack(false);//接著對祖先節(jié)點進行顏色反轉node = grandFather;continue;}/*** 如果沒有觸發(fā)顏色反轉，需要進行左旋、右旋操作*/if (node == father.getRight()){//左旋leftRotate(father);RedBlackNode temp = node;node = father;father = temp;}father.setBlack(true);grandFather.setBlack(false);rightRotate(grandFather);}else {RedBlackNode uncle = grandFather.getLeft();if (uncle != null && uncle.isBlack() == false){father.setBlack(true);uncle.setBlack(true);grandFather.setBlack(false);node = grandFather;continue;}if (node == father.getLeft()){rightRotate(father);RedBlackNode temp = node;node = father;father = temp;}father.setBlack(true);grandFather.setBlack(false);leftRotate(grandFather);}}root.setBlack(true);}public void leftRotate(RedBlackNode node){RedBlackNode right = node.getRight();RedBlackNode parent = node.getParent();if (parent == null){root = right;right.setParent(null);}else {if (parent.getLeft() != null && parent.getLeft() == node){parent.setLeft(right);}else {parent.setRight(right);}right.setParent(parent);}node.setParent(right);node.setRight(right.getLeft());if (right.getLeft() != null){right.getLeft().setParent(node);}right.setLeft(node);}private void rightRotate(RedBlackNode node){RedBlackNode left = node.getLeft();RedBlackNode parent = node.getParent();if (parent == null){root = left;left.setParent(null);}else {if (parent.getLeft() != null && parent.getLeft() == node){parent.setLeft(left);}else {parent.setRight(left);}left.setParent(left);}node.setParent(left);node.setLeft(left.getRight());if (left.getRight() != null){left.getRight().setParent(node);}left.setRight(node);}@Overridepublic void deleteNode(RedBlackNode root, RedBlackNode node) {}@Overridepublic void preOrder(List<Integer> showList, RedBlackNode node) {if(node == null) {return ;}//葉子if(node.getLeft() == null && node.getRight()==null){showList.add(node.getData());return ;}showList.add(node.getData());//遞歸 左孩子preOrder(showList, node.getLeft());//遞歸 右孩子preOrder(showList, node.getRight());}@Overridepublic void inOrder(List<Integer> showList, RedBlackNode node) {if(node == null) {return ;}//葉子if(node.getLeft() == null && node.getRight()==null){showList.add(node.getData());return ;}//遞歸 左孩子inOrder(showList, node.getLeft());showList.add(node.getData());//遞歸 右孩子inOrder(showList, node.getRight());}@Overridepublic void laOrder(List<Integer> showList, RedBlackNode node) {if(node == null) {return ;}//葉子if(node.getLeft() == null && node.getRight()==null){showList.add(node.getData());return ;}//遞歸 左孩子laOrder(showList, node.getLeft());//遞歸 右孩子laOrder(showList, node.getRight());showList.add(node.getData());}@Overridepublic void bfs(List<Integer> list, RedBlackNode node) {if (node == null){return;}LinkedList<RedBlackNode> queue = new LinkedList<>();queue.offer(node);while (!queue.isEmpty()){RedBlackNode child = queue.poll();list.add(child.data);if (child.left != null){queue.offer(child.left);}if (child.right != null){queue.offer(child.right);}}} }

單元測試

package csdn.dreamzuora.tree;import org.junit.Before; import org.junit.Test; import org.junit.jupiter.api.Assertions;import java.util.ArrayList; import java.util.Arrays; import java.util.List;import static org.junit.Assert.*;/*** Title:* Description:** @version 1.0* @author: weijie* @date: 2020/10/22 14:31*/ public class RedBlackTreeTest {RedBlackTree RBtree = new RedBlackTree();@Beforepublic void init() {List<Integer> list = Arrays.asList(10, 5, 9, 3, 6, 7, 19, 32, 24, 17);RBtree.createTree(list);}@Testpublic void addNode(){}@Testpublic void deleteNode() {}@Testpublic void preOrder() {List<Integer> actualList = new ArrayList<>();RBtree.preOrder(actualList, RBtree.root);List<Integer> expectList = Arrays.asList(9, 5, 3, 6, 7, 19, 10, 17, 32, 24);Assertions.assertEquals(expectList, actualList);}@Testpublic void inOrder() {List<Integer> actualList = new ArrayList<>();RBtree.inOrder(actualList, RBtree.root);List<Integer> expectList = Arrays.asList(3, 5, 6, 7, 9, 10, 17, 19, 24, 32);Assertions.assertEquals(expectList, actualList);}@Testpublic void laOrder() {List<Integer> actualList = new ArrayList<>();RBtree.laOrder(actualList, RBtree.root);List<Integer> expectList = Arrays.asList(3, 7, 6, 5, 17, 10, 24, 32, 19, 9);Assertions.assertEquals(expectList, actualList);}@Testpublic void bfs() {List<Integer> actualList = new ArrayList<>();RBtree.bfs(actualList, RBtree.root);List<Integer> expectList = Arrays.asList(9, 5, 19, 3, 6, 10, 32, 7, 17, 24);Assertions.assertEquals(expectList, actualList);}@Testpublic void leftRotate(){}@Testpublic void rightRotate(){RedBlackNode node5 = new RedBlackNode(5);RedBlackNode node3 = new RedBlackNode(3);RedBlackNode node8 = new RedBlackNode(8);RedBlackNode node7 = new RedBlackNode(7);RedBlackNode node9 = new RedBlackNode(9);RBtree.root = node5;RBtree.root.left = node3;node8.left = node7;node8.right = node9;RBtree.root.right = node8;RBtree.leftRotate(RBtree.root);} }

總結

以上是生活随笔為你收集整理的红黑树 java代码实现的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內容還不錯，歡迎將生活随笔推薦給好友。