`
啸笑天
  • 浏览: 3465659 次
  • 性别: Icon_minigender_1
  • 来自: China
社区版块
存档分类
最新评论

【code】java红黑树

阅读更多

 

import java.util.*;

public class RedBlackTree<T extends Comparable>
{
	//定义红黑树的颜色
	private static final boolean RED   = false;
	private static final boolean BLACK = true;
	static class Node
	{
		Object data;
		Node parent; 
		Node left;
		Node right;
		//节点的默认颜色是黑色
		boolean color = BLACK;
		public Node(Object data , Node parent 
			, Node left , Node right)
		{
			this.data = data;
			this.parent = parent;
			this.left = left;
			this.right = right;
		}
		public String toString()
		{
			return "[data=" + data
				+ ", color=" + color + "]"; 
		}
		public boolean equals(Object obj)
		{
			if (this == obj)
			{
				return true;
			}
			if (obj.getClass() == Node.class)
			{
				Node target = (Node)obj;
				return data.equals(target.data)
					&& color == target.color
					&& left == target.left
					&& right == target.right
					&& parent == target.parent;
			}
			return false;
		}
	}
	private Node root;
	//两个构造器用于创建排序二叉树
	public RedBlackTree()
	{
		root = null;
	}
	public RedBlackTree(T o)
	{
		root = new Node(o , null , null , null);
	}
	//添加节点
	public void add(T ele)
	{
		//如果根节点为null
		if (root == null)
		{
			root = new Node(ele , null , null , null);
		}
		else
		{
			Node current = root;
			Node parent = null;
			int cmp = 0;
			//搜索合适的叶子节点,以该叶子节点为父节点添加新节点
			do
			{
				parent = current;
				cmp = ele.compareTo(current.data);
				//如果新节点的值大于当前节点的值
				if (cmp > 0)
				{
					//以右子节点作为当前节点
					current = current.right;
				}
				//如果新节点的值小于当前节点的值
				else
				{
					//以左子节点作为当前节点
					current = current.left;
				}
			}
			while (current != null);
			//创建新节点
			Node newNode = new Node(ele , parent , null , null);
			//如果新节点的值大于父节点的值
			if (cmp > 0)
			{
				//新节点作为父节点的右子节点
				parent.right = newNode;
			}
			//如果新节点的值小于父节点的值
			else
			{
				//新节点作为父节点的左子节点
				parent.left = newNode;
			}
			//维护红黑树
			fixAfterInsertion(newNode);
		}
	}
	//删除节点
	public void remove(T ele)
	{
		//获取要删除的节点
		Node target = getNode(ele);
		//如果被删除节点的左子树、右子树都不为空
		if (target.left != null && target.right != null) 
		{
			//找到target节点中序遍历的前一个节点
			//s用于保存target节点的左子树中值最大的节点
			Node s = target.left;
			//搜索target节点的左子树中值最大的节点
			while (s.right != null)
			{
				s = s.right;
			}
			//用s节点来代替p节点
			target.data = s.data;
			target = s;
		} 
		//开始修复它的替换节点,如果该替换节点不为null
		Node replacement = (target.left != null ? target.left : target.right);
		if (replacement != null) 
		{
			// 让replacement的parent指向target的parent
			replacement.parent = target.parent;
			//如果target的parent为null,表明target本身是根节点
			if (target.parent == null)
			{
				root = replacement;
			}
			//如果target是其父节点的左子节点
			else if (target == target.parent.left)
			{
				//让target的父节点left指向replacement
				target.parent.left  = replacement;
			}
			//如果target是其父节点的右子节点
			else
			{
				//让target的父节点right指向replacement
				target.parent.right = replacement;
			}
			//彻底删除target节点
			target.left = target.right = target.parent = null;

			// 修复红黑树
			if (target.color == BLACK)
			{
				fixAfterDeletion(replacement);
			}
		}
		//target本身是根节点
		else if (target.parent == null) 
		{
			root = null;
		} 
		else 
		{
			//target没有子节点,把它当成虚的替换节点。
			//修复红黑树
			if (target.color == BLACK)
			{
				fixAfterDeletion(target);
			}
			if (target.parent != null) 
			{
				//如果target是其父节点的左子节点
				if (target == target.parent.left)
				{
					//将target的父节点left设为null
					target.parent.left = null;
				}
				//如果target是其父节点的右子节点
				else if (target == target.parent.right)
				{
					//将target的父节点right设为null
					target.parent.right = null;
				}
				//将target的parent设置null
				target.parent = null;
			}
		}
	}
	//根据给定的值搜索节点
	public Node getNode(T ele)
	{
		//从根节点开始搜索
		Node p = root;
		while (p != null) 
		{
			int cmp = ele.compareTo(p.data);
			//如果搜索的值小于当前p节点的值
			if (cmp < 0)
			{
				//向左子树搜索
				p = p.left;
			}
			//如果搜索的值大于当前p节点的值
			else if (cmp > 0)
			{
				//向右子树搜索
				p = p.right;
			}
			else
			{
				return p;
			}
		}
		return null;
	}
	//广度优先遍历
	public List<Node> breadthFirst()
	{
		Queue<Node> queue = new ArrayDeque<Node>();
		List<Node> list = new ArrayList<Node>();
		if( root != null)
		{
			//将根元素入“队列”
			queue.offer(root);
		}
		while(!queue.isEmpty())
		{
			//将该队列的“队尾”的元素添加到List中
			list.add(queue.peek());
			Node p = queue.poll();
			//如果左子节点不为null,将它入“队列”
			if(p.left != null)
			{
				queue.offer(p.left);
			}
			//如果右子节点不为null,将它入“队列”
			if(p.right != null)
			{
				queue.offer(p.right);
			}
		}
		return list;
	}
	//插入节点后修复红黑树
	private void fixAfterInsertion(Node x) 
	{
		x.color = RED;
		//直到x节点的父节点不是根,且x的父节点不是红色
		while (x != null && x != root 
			&& x.parent.color == RED) 
		{
			//如果x的父节点是其父节点的左子节点
			if (parentOf(x) == leftOf(parentOf(parentOf(x)))) 
			{
				//获取x的父节点的兄弟节点
				Node y = rightOf(parentOf(parentOf(x)));
				//如果x的父节点的兄弟节点是红色
				if (colorOf(y) == RED) 
				{
					//将x的父节点设为黑色
					setColor(parentOf(x), BLACK);
					//将x的父节点的兄弟节点设为黑色
					setColor(y, BLACK);
					//将x的父节点的父节点设为红色
					setColor(parentOf(parentOf(x)), RED);
					x = parentOf(parentOf(x));
				}
				//如果x的父节点的兄弟节点是黑色
				else
				{
					//如果x是其父节点的右子节点
					if (x == rightOf(parentOf(x))) 
					{
						//将x的父节点设为x
						x = parentOf(x);
						rotateLeft(x);
					}
					//把x的父节点设为黑色
					setColor(parentOf(x), BLACK);
					//把x的父节点的父节点设为红色
					setColor(parentOf(parentOf(x)), RED);
					rotateRight(parentOf(parentOf(x)));
				}
			} 
			//如果x的父节点是其父节点的右子节点
			else 
			{
				//获取x的父节点的兄弟节点
				Node y = leftOf(parentOf(parentOf(x)));
				//如果x的父节点的兄弟节点是红色
				if (colorOf(y) == RED) 
				{
					//将x的父节点设为黑色。
					setColor(parentOf(x), BLACK);
					//将x的父节点的兄弟节点设为黑色
					setColor(y, BLACK);
					//将x的父节点的父节点设为红色
					setColor(parentOf(parentOf(x)), RED);
					//将x设为x的父节点的节点
					x = parentOf(parentOf(x));
				}
				//如果x的父节点的兄弟节点是黑色
				else 
				{
					//如果x是其父节点的左子节点
					if (x == leftOf(parentOf(x))) 
					{
						//将x的父节点设为x
						x = parentOf(x);
						rotateRight(x);
					}
					//把x的父节点设为黑色
					setColor(parentOf(x), BLACK);
					//把x的父节点的父节点设为红色
					setColor(parentOf(parentOf(x)), RED);
					rotateLeft(parentOf(parentOf(x)));
				}
			}
		}
		//将根节点设为黑色
		root.color = BLACK;
	}
	//删除节点后修复红黑树
	private void fixAfterDeletion(Node x) 
	{
		//直到x不是根节点,且x的颜色是黑色
		while (x != root && colorOf(x) == BLACK) 
		{
			//如果x是其父节点的左子节点
			if (x == leftOf(parentOf(x)))
			{
				//获取x节点的兄弟节点
				Node sib = rightOf(parentOf(x));
				//如果sib节点是红色
				if (colorOf(sib) == RED)
				{
					//将sib节点设为黑色
					setColor(sib, BLACK);
					//将x的父节点设为红色
					setColor(parentOf(x), RED);
					rotateLeft(parentOf(x));
					//再次将sib设为x的父节点的右子节点
					sib = rightOf(parentOf(x));
				}
				//如果sib的两个子节点都是黑色
				if (colorOf(leftOf(sib)) == BLACK
					&& colorOf(rightOf(sib)) == BLACK) 
				{
					//将sib设为红色
					setColor(sib, RED);
					//让x等于x的父节点
					x = parentOf(x);
				} 
				else 
				{
					//如果sib的只有右子节点是黑色
					if (colorOf(rightOf(sib)) == BLACK) 
					{
						//将sib的左子节点也设为黑色
						setColor(leftOf(sib), BLACK);
						//将sib设为红色
						setColor(sib, RED);
						rotateRight(sib);
						sib = rightOf(parentOf(x));
					}
					//设置sib的颜色与x的父节点的颜色相同
					setColor(sib, colorOf(parentOf(x)));
					//将x的父节点设为黑色
					setColor(parentOf(x), BLACK);
					//将sib的右子节点设为黑色
					setColor(rightOf(sib), BLACK);
					rotateLeft(parentOf(x));
					x = root;
				}
			}
			//如果x是其父节点的右子节点
			else
			{
				//获取x节点的兄弟节点
				Node sib = leftOf(parentOf(x));
				//如果sib的颜色是红色
				if (colorOf(sib) == RED) 
				{
					//将sib的颜色设为黑色
					setColor(sib, BLACK);
					//将sib的父节点设为红色
					setColor(parentOf(x), RED);
					rotateRight(parentOf(x));
					sib = leftOf(parentOf(x));
				}
				//如果sib的两个子节点都是黑色
				if (colorOf(rightOf(sib)) == BLACK 
					&& colorOf(leftOf(sib)) == BLACK) 
				{
					//将sib设为红色
					setColor(sib, RED);
					//让x等于x的父节点
					x = parentOf(x);
				}
				else 
				{
					//如果sib只有左子节点是黑色
					if (colorOf(leftOf(sib)) == BLACK) 
					{
						//将sib的右子节点也设为黑色
						setColor(rightOf(sib), BLACK);
						//将sib设为红色
						setColor(sib, RED);
						rotateLeft(sib);
						sib = leftOf(parentOf(x));
					}
					//将sib的颜色设为与x的父节点颜色相同
					setColor(sib, colorOf(parentOf(x)));
					//将x的父节点设为黑色
					setColor(parentOf(x), BLACK);
					//将sib的左子节点设为黑色
					setColor(leftOf(sib), BLACK);
					rotateRight(parentOf(x));
					x = root;
				}
			}
		}
		setColor(x, BLACK);
	}
	//获取指定节点的颜色
	private boolean colorOf(Node p)
	{
		return (p == null ? BLACK : p.color);
	}
	//获取指定节点的父节点
	private Node parentOf(Node p) 
	{
		return (p == null ? null: p.parent);
	}
	//为指定节点设置颜色
	private void setColor(Node p, boolean c)
	{
		if (p != null)
		{
			p.color = c;
		}
	}
	//获取指定节点的左子节点
	private Node leftOf(Node p) 
	{
		return (p == null) ? null: p.left;
	}
	//获取指定节点的右子节点
	private Node rightOf(Node p) 
	{
		return (p == null) ? null: p.right;
	}
	/**
	 * 执行如下转换
	 *  p        r
	 *     r   p   
	 *  q        q
	 */
	private void rotateLeft(Node p) 
	{
		if (p != null) 
		{
			//取得p的右子节点
			Node r = p.right;
			Node q = r.left;
			//将r的左子节点链到p的右节点链上
			p.right = q;
			//让r的左子节点的parent指向p节点
			if (q != null)
			{
				q.parent = p;
			}
			r.parent = p.parent;
			//如果p已经是根节点
			if (p.parent == null)
			{
				root = r;
			}
			//如果p是其父节点的左子节点
			else if (p.parent.left == p)
			{
				//将r设为p的父节点的左子节点
				p.parent.left = r;
			}
			else
			{
				//将r设为p的父节点的右子节点
				p.parent.right = r;
			}
			r.left = p;
			p.parent = r;
		}
	}
	/**
	 * 执行如下转换
	 *     p       l
	 *  l              p
	 *     q       q
	 */
	private void rotateRight(Node p) 
	{
		if (p != null)
		{
			//取得p的左子节点
			Node l = p.left;
			Node q = l.right;
			//将l的右子节点链到p的左节点链上
			p.left = q;
			//让l的右子节点的parent指向p节点
			if (q != null) 
			{
				q.parent = p;
			}
			l.parent = p.parent;
			//如果p已经是根节点
			if (p.parent == null)
			{
				root = l;
			}
			//如果p是其父节点的右子节点
			else if (p.parent.right == p)
			{
				//将l设为p的父节点的右子节点
				p.parent.right = l;
			}
			else 
			{
				//将l设为p的父节点的左子节点
				p.parent.left = l;
			}
			l.right = p;
			p.parent = l;
		}
	}
	//实现中序遍历
	public List<Node> inIterator()
	{
		return inIterator(root);
	}
	private List<Node> inIterator(Node node)
	{
		List<Node> list = new ArrayList<Node>();
		//递归处理左子树
		if (node.left != null)
		{
			list.addAll(inIterator(node.left));
		}
		//处理根节点
		list.add(node);
		//递归处理右子树
		if (node.right != null)
		{
			list.addAll(inIterator(node.right));
		}
		return list;
	}
	
	public static void main(String[] args) 
	{
		RedBlackTree<Integer> tree 
			= new RedBlackTree<Integer>();
		//添加节点
		tree.add(5);
		tree.add(20);
		tree.add(10);
		tree.add(3);
		tree.add(8);
		tree.add(15);
		tree.add(30);
		System.out.println(tree.breadthFirst());
		//删除节点
		tree.remove(20);
		System.out.println(tree.breadthFirst());
//		System.out.println(tree.inIterator());
		
	}
}
  • 描述: 1
  • 大小: 109.9 KB
  • 描述: 3
  • 大小: 108.6 KB
  • 描述: 2
  • 大小: 1.4 MB
  • 描述: 4
  • 大小: 116.4 KB
  • 描述: 5
  • 大小: 107.4 KB
  • 描述: 6
  • 大小: 91.8 KB
  • 描述: 7
  • 大小: 19.5 KB
分享到:
评论

相关推荐

    红黑树源码

    红黑树(Red-Black Tree)是一种自平衡的二叉查找树,它的设计目标是确保在最坏的情况下,树的搜索、插入和删除操作的时间复杂度都能够保持在O(log n)。这种数据结构广泛应用于各种操作系统和编程语言的库中,如C++ ...

    matlab_ 红黑树二分搜索法示例,用于比较C++、Java、Python、Ruby和MATLAB代码

    红黑树二分搜索法示例,用于比较C++、Java、Python、Ruby和MATLAB代码 Comparison of C++, Java, Python, Ruby and MATLAB OOP Example RedBlack Tree Binary Search Example Used to Compare of C++, Java, ...

    rbtree-ui-code.zip

    `DrawTree.java` 文件可能是用于可视化红黑树的工具,使用Java图形用户界面(GUI)库来动态展示红黑树的插入和删除过程。通常,这个工具会包含一个类,用于创建和管理图形界面,以及处理用户的交互事件,如点击按钮...

    Java_Programming_classic_tree_parameter_code.rar_java programmin

    在Java中,`java.util.TreeSet`和`java.util.TreeMap`是基于红黑树实现的集合类,提供了排序和高效的查找功能。此外,`java.awt.Tree`和`javax.swing.JTree`用于图形用户界面中的树视图展示。 6. **应用场景** 树...

    collectionJava源码-collection-source-code-analyze:Java集合类源代码分析

    collection-source-code-analyze(Java集合类源代码分析) 对集合类源代码进行分析主要对增删改查操作的源代码进行分析, 因为这四个操作才是集合中最重要的, 其它的操作示情况进行分析, 分析的流程我采用的是自己仿照...

    TreeNode-SourceCode.7z

    而`TreeNode`类是`HashMap8`(通常指的是`java.util.HashMap`的早期版本,8可能是其内部版本号)中的一个关键内部类,它用于实现哈希表的红黑树结构。当`HashMap`中的元素数量超过特定阈值时,为了保持性能,`...

    data structures with java source code

    Java中的TreeSet和TreeMap类利用红黑树(一种自平衡的二叉查找树)来实现高效的操作。 9. **图(Graph)**:图由节点和边构成,用于表示对象之间的关系。Java中并没有内置的图数据结构,但可以通过邻接矩阵或邻接表...

    Java软件结构 设计和使用数据结构

    在"ch07 Code"和"ch08 Code"中,可能会讨论到树形数据结构,如二叉树和红黑树。二叉树是每个节点最多有两个子节点的数据结构,广泛应用于搜索和排序。红黑树是一种自平衡的二叉查找树,确保插入和删除操作的时间...

    自定义map实现java的hashmap

    - 处理冲突:当多个键的哈希码对应同一个索引时,我们需要将这些键值对存储在一个链表或红黑树中,以便于后续查找。 - 插入操作:为键值对插入HashMap,首先计算哈希码,然后找到对应的数组位置,如果该位置为空,...

    Cracking-the-code-interview-solution-java.rar_The Interview_crac

    CtCI涵盖了各种常见数据结构,如数组、链表、栈、队列、树(二叉树、平衡树如AVL和红黑树)、图等。理解它们的特性、操作时间复杂度以及如何在实际问题中应用是关键。例如,链表操作可以用于实现LRU缓存,二叉树可以...

    java数据结构源码-DataStructure_javaCode:数据结构java

    二叉树、红黑树等都是常见的树类型,Java的`java.util.TreeSet`和`java.util.TreeMap`使用了红黑树。 6. **图**:由顶点和边组成,可以表示复杂的关联关系。Java中通常通过邻接矩阵或邻接表来实现图。 通过阅读和...

    java源码剖析-Java-source-code-analysis:Java数据结构的源代码分析

    红黑树是一种自平衡二叉查找树,它确保任何节点到其叶子节点的最长路径不超过最短路径的两倍,从而保证了操作的近似O(log n)时间复杂度。 标签“系统开源”意味着这些源码是开放的,开发者可以自由地查看、学习和...

    java源码结构-Java-data-structure-source-code:Java数据结构

    Java集合框架中的TreeSet和TreeMap就是基于红黑树实现的。 6. **图**:图由顶点和边组成,用于表示对象之间的关系。Java没有内置的图数据结构,通常使用邻接矩阵或邻接表来实现。 7. **哈希表**:哈希表提供快速的...

    算法实践(JavaScript & Java),排序,查找、树、两指针、动态规划等

    树是数据结构的基础,包括二叉树、平衡二叉树(AVL、红黑树)、B树、B+树等。它们在文件系统、数据库索引、搜索算法等方面有广泛应用。在JavaScript和Java中,可以通过对象或类表示树节点,并实现遍历(深度优先、...

    java.util源码-java-source-code:java.util源码阅读

    - **TreeMap/TreeSet**:基于红黑树的有序映射和集合,提供排序功能和O(log n)的时间复杂度。 2. 日期时间: - **Calendar**:抽象类,是日期和时间计算的基础,提供了丰富的日期时间操作。 - **Date**:表示...

    2021 java面试题.pdf

    HashMap的实现基于散列表,Java 7和8的实现主要区别在于解决哈希冲突的方式,Java 8引入了红黑树。 HashMap死循环可能由迭代器的并发修改引起,ConcurrentHashMap是线程安全的HashMap实现。 静态代理和动态代理的...

    java类源码-java-study-sourcecode:Java各类知识的学习

    这个模块可能包含常见的数据结构,如数组、链表、栈、队列、堆、树(二叉树、红黑树等)、图等。通过源码学习,你可以看到这些数据结构如何在Java中实现,以及如何根据实际问题选择合适的数据结构。 IO学习是Java...

    Java软件结构与数据结构(第三版)源代码

    在Java中,数据结构通常包括数组、链表、栈、队列、散列表、树(二叉树、平衡树如AVL树和红黑树)、图等。这些数据结构在实际问题解决中有着广泛的应用,比如搜索、排序、图形算法等。书中可能会详细讲解每个数据...

    interview-Java-code:Java代码集合

    - 树:二叉树的遍历(前序、中序、后序)、平衡树(AVL、红黑树)操作。 - 图:深度优先搜索(DFS)和广度优先搜索(BFS)。 - 排序算法:快速排序、归并排序、堆排序、冒泡排序、选择排序等。 - 查找算法:二分...

    数据结构与问题分析 java 源代码

    `Tree`相关文件(如`TestTreeIterators.java`)可能涉及二叉树、平衡树(如AVL树或红黑树)等,它们在搜索、排序和其他操作中非常高效。 2. **问题分析**:这是理解算法复杂性和性能的过程。`Sort.java`可能是对...

Global site tag (gtag.js) - Google Analytics