文章目录

代码实现

节点实现类

package csdn.dreamzuora.tree;/*** Title:* Description:** @version 1.0* @author: weijie* @date: /10/19 13:30*/public interface Node {}

package csdn.dreamzuora.tree;import java.io.Serializable;/*** Title:* Description:** @version 1.0* @author: weijie* @date: /10/19 13:27*/public abstract class AbstractNode<T, E> implements Node, Serializable {private static final long serialVersionUID = -2321782309212147194L;/*** 数据域*/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: 红黑树节点* Description:** @version 1.0* @author: weijie* @date: /10/21 14:36*/public class RedBlackNode extends AbstractNode<Integer, RedBlackNode> {/*** 红黑树节点颜色标记*/boolean isBlack;/*** 红黑树父亲节点*/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 +'}';}}

红黑树实现

package csdn.dreamzuora.tree;import java.util.List;/*** Title: 树接口* Description:** @version 1.0* @author: weijie* @date: /10/16 14:56*/public interface Tree<T,E> {/*** 构建树* @param dataList*/void createTree(List<T> dataList);/*** 添加节点* @param data*/E addNode(E tree, T data);/*** 删除节点* @param tree* @param node*/void deleteNode(E tree, E node);/*** 前序遍历:根节点->左节点->右节点*/void preOrder(List<T> list, E node);/*** 中序遍历：左节点->根节点->右节点* @return*/void inOrder(List<T> list, E node);/*** 后序遍历：左节点->右节点->根节点*/void laOrder(List<T> list, E node);/*** 广度优先遍历：层序遍历* @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: /10/16 14:57*/public abstract class AbstractTree<T, E> implements Tree<T, E>, Serializable {private static final long serialVersionUID = -8046156919125106629L;/*** 根节点*/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:* 规则：* 1.每个节点不是红色就是黑色* 2.每个根节点是黑色* 3.每个叶子节点就是黑色的空节点* 4.如果一个节点是红色的，则它的子节点必须是黑色的(父子不能同为红)* 5.平衡的关键字：从任一节点到其每个叶子的所有路径都包含相同的黑色的节点* 6.新插入节点默认为红色，插入后需要校验红黑树是否符合规则，不符合则需要进行平衡** 再平衡涉及到：左旋、右旋、颜色反转** 红黑树插入分为五种情况：** 1.新节点(A)位于树根，没有父节点* 直接让新节点变成黑色，规则二得到满足，同时，黑色的根节点使得每条路径上的黑色节点数目都增加1，所以* 并没有打破规则5*A(红) -> A(黑)* 1 2 1 2*** 2.新节点(B)的父节点是黑色* 新插入的红色结点B并没有打破红黑树的规则，所以不需要做任何调整*A(黑)* B(红) 3*1 2*** 3.新节点(D)的父节点和叔叔节点都是红色* A(黑)A(黑) A(红)* B(红) C(红) -> B(黑) C(红) -> ... ->B(黑) c(黑)*D(红) 3 4 5 D(红) D(红)*1 2*经过上面的调整，这一局部重新符合了红黑树的规则* 4.新节点(D)的父节点是红色，叔叔节点是黑色或者没有叔叔，且新节点是父节点的右孩子，父节点(B)是祖父节点的左孩子* 我们以节点B为轴，做一次左旋，使得节点D成为父节点，原来的父节点B成为D的左孩子* A(黑) A(黑)* B(红) C(黑) -> D(红) C(黑)* 1 D(红) 4 5B(红) 3 4 5*2 3 1 2** 5.新节点(D)的父节点是红色，叔叔节点是黑色或者没有叔叔，且新节点是父节点的左孩子，父节点（B）* 是祖父节点的左孩子* 我们以节点A为抽，做一次右旋转，使得节点B成为祖父节点，节点A成为节点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 54 5** 颜色反转：* 如果当前节点、父节点、叔叔节点同为红色，这种情况违反了红黑树的规则，需求将红色向祖辈上传，* 父节点和叔叔节点变为黑色，爷爷节点变为黑->红色** 左旋：逆时针旋转红黑树的两个节点，使得父节点被自己的右孩子取代，而自己成为自己的左孩子*** 右旋：顺时针旋转红黑树的两个节点，使得父节点被自己的左孩子取代，而自己成为自己的右孩子** 时间负责度：logn* @version 1.0* @author: weijie* @date: /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;/*** 判断新节点是放在左子树还是右子树*/if (data <= parent.getData()){son = parent.getLeft();}else {son = parent.getRight();}/*** 对树深度遍历，寻找新节点存放的位置*/while (son != null){parent = son;if (data <= parent.getData()){son = parent.getLeft();}else {son = parent.getRight();}}/*** 节点插入*/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;/*** 获取父节点并判断父节点是否为红色节点，规则：父子不同为红*/while ((father = node.getParent()) != null && father.isBlack() == false){//获取祖父节点grandFather = father.getParent();//判断父节点在祖先节点存在的位置if (grandFather.getLeft() == father){//叔叔节点RedBlackNode uncle = grandFather.getRight();//如果父亲、叔叔节点存在且都为红，则父亲、叔叔节点变为黑色if (uncle != null && uncle.isBlack() == false){father.setBlack(true);uncle.setBlack(true);grandFather.setBlack(false);//接着对祖先节点进行颜色反转node = grandFather;continue;}/*** 如果没有触发颜色反转，需要进行左旋、右旋操作*/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: /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代码实现》对你有帮助，请点赞、收藏，并留下你的观点哦！