红黑树-java实现

引言

根据《算法》第4版。编写红黑树。

理论

参见:

浅谈算法和数据结构: 八 平衡查找树之2-3树

浅谈算法和数据结构: 九 平衡查找树之红黑树

这些也是参考的《算法》

特性

红黑数事实上就是特殊的二叉排序树。

红黑树是一种具有红色和黑色链接的平衡查找树，同时满足： - 红色节点向左倾斜 - 一个节点不可能有两个红色链接 - 整个书完全黑色平衡，即从根节点到所以叶子结点的路径上，黑色链接的个数都相同。

代码（java）

package org.hirudy.practice; /** * @author: rudy * @date: 2016/08/13 * * 红黑树实现 * */ public class RedBlackTreePractice { /** * 红黑数节点 * @param <T> */ private static class Node<T> { public static final boolean RED_NODE = true; public static final boolean BLACK_NODE = false; public boolean nodeColor; // 节点颜色 public Comparable key; // 当前节点搜索key public T value; // 当前节点存储值 public int nodeNumber = 0; // 以当前节点为根节点的子树的节点个数 public Node leftNode,rightNode; // 当前节点的左右子节点 public Node(Comparable key, T value,int number, boolean color){ this.key = key; this.value = value; this.nodeNumber = number; this.nodeColor = color; } /** * 判断当前节点类型 * @return boolean */ public boolean isRed(){ return this.nodeColor == RED_NODE; } /** * 获取当前节点及其子节点个数 * @return int */ public int getSize(){ return nodeNumber; } /** * 计算当前节点及其子节点个数 * @return int */ protected int size(){ int nodeNumber = 1; if (leftNode != null){ nodeNumber += leftNode.getSize(); } if (rightNode != null){ nodeNumber += rightNode.getSize(); } return nodeNumber; } } /** * 红黑数 * @param <T> */ public static class RedBlackTree<T> { private Node<T> root; // 根节点 /** * 红黑树基本操作-左旋转 * @param Node<T> node * @return Node<T> */ protected Node rotateLeft(Node node){ Node tmp = node.rightNode; node.rightNode = tmp.leftNode; tmp.leftNode = node; tmp.nodeColor = node.nodeColor; node.nodeColor = Node.RED_NODE; tmp.nodeNumber = node.nodeNumber; node.nodeNumber = node.size(); return tmp; } /** * 红黑树基本操作-右旋转 * @param Node<T> node * @return Node<T> */ protected Node rotateRight(Node node){ Node tmp = node.leftNode; node.leftNode = tmp.rightNode; tmp.rightNode = node; tmp.nodeColor = node.nodeColor; node.nodeColor = Node.RED_NODE; tmp.nodeNumber = node.nodeNumber; node.nodeNumber = node.size(); return tmp; } /** * 红黑树基本操作-颜色旋转 * @param Node<T> node * @return Node<T> */ protected Node rotateColor(Node node){ node.nodeColor = Node.RED_NODE; node.leftNode.nodeColor = Node.BLACK_NODE; node.rightNode.nodeColor = Node.BLACK_NODE; return node; } /** * 判断节点是否为红节点 * @param node * @return */ protected boolean isRed(Node node){ if (node == null){ return false; } return node.isRed(); } public Node<T> search(Comparable key){ return search(key,this.root); } /** * 查询 * @param key 查询关键字 * @param node 开始查询的根节点 * @return Node 查找到的节点 */ public Node<T> search(Comparable key, Node node){ if (node == null){ return null; } int cmp = key.compareTo(node.key); if (cmp < 0){ return search(key,node.leftNode); }else if (cmp > 0){ return search(key,node.rightNode); }else{ return node; } } /** * 从根节点插入 * @param key * @param value */ public void insert(Comparable key, T value){ Node<T> node = insertSubTree(this.root, key, value); node.nodeColor = Node.BLACK_NODE; this.root = node; } /** * 从某个节点插入 * @param key 插入key * @param value 插入值 */ protected Node insertSubTree(Node node, Comparable key, T value){ if (node == null){ return new Node<T>(key, value, 1, Node.RED_NODE); } // 比较各个节点 int cmp = key.compareTo(node.key); if (cmp < 0){ node.leftNode = insertSubTree(node.leftNode, key, value); }else if (cmp > 0){ node.rightNode = insertSubTree(node.rightNode, key, value); }else{ node.value = value; } if (!isRed(node.leftNode) && isRed(node.rightNode)){ node = rotateLeft(node); } if (isRed(node.leftNode) && isRed(node.leftNode.leftNode)){ node = rotateRight(node); } if (isRed(node.leftNode) && isRed(node.rightNode)){ node = rotateColor(node); } node.nodeNumber = node.size(); return node; } } public static void main(String[] args){ RedBlackTree<String> tree = new RedBlackTree<String>(); int[] insertValue = new int[]{12,1,9,10,77,2,38,8,4}; for (int value : insertValue){ tree.insert(value,"value_" + value); } Node node = tree.search(77); System.out.println(node.value); System.out.println("end"); } }