红黑树红黑树的java实现？

avl树和红黑树的特点比较

由于AVL树种类较少所以比红黑树实际上更容易实现.而且ALV树在旋转插入所需要的复杂度为0(1),而红 　　黑树则需要的复杂度为0(lgn). 　　实际上插入AVL树和红黑树的速度取决于你所插入的数据.如果你的数据分布较好,则比较宜于采用AVL树(例如随机产生系列数), 　　但是如果你想处理比较杂乱的情况,则红黑树是比较快的,因为红黑树对已经处理好的数据重新平衡减少了不心要的操作.另外一方面, 　　如果是一种非寻常的插入系列比较常见(比如,插入密钥系列),则AVL树比较快,因为它的严格的平衡规则将会减少树的高度. 你可以去这里看看/page/M0/S568/568044.html

java中哪些数据结构使用了红黑树

参考资料的网页上有比较的代码,你可以仔细看下~~~ java中HashMap,LinkedHashMap,TreeMap，HashTable的区别 java为数据结构中的映射定义了一个接口java.util.Map;它有四个实现类,分别是HashMap Hashtable LinkedHashMap 和TreeMap Map主要用于存储健值对，根据键得到值，因此不允许键重复(重复了覆盖了),但允许值重复。

Hashmap 是一个最常用的Map,它根据键的HashCode 值存储数据,根据键可以直接获取它的值，具有很快的访问速度，遍历时，取得数据的顺序是完全随机的。

HashMap最多只允许一条记录的键为Null;允许多条记录的值为 Null;HashMap不支持线程的同步，即任一时刻可以有多个线程同时写HashMap;可能会导致数据的不一致。

如果需要同步，可以用 Collections的synchronizedMap方法使HashMap具有同步的能力，或者使用ConcurrentHashMap。

Hashtable与 HashMap类似,它继承自Dictionary类，不同的是:它不允许记录的键或者值为空;它支持线程的同步，即任一时刻只有一个线程能写Hashtable,因此也导致了 Hashtable在写入时会比较慢。

LinkedHashMap保存了记录的插入顺序，在用Iterator遍历LinkedHashMap时，先得到的记录肯定是先插入的.也可以在构造时用带参数，按照应用次数排序。

在遍历的时候会比HashMap慢，不过有种情况例外，当HashMap容量很大，实际数据较少时，遍历起来可能会比LinkedHashMap慢，因为LinkedHashMap的遍历速度只和实际数据有关，和容量无关，而HashMap的遍历速度和他的容量有关。

TreeMap实现SortMap接口，能够把它保存的记录根据键排序,默认是按键值的升序排序，也可以指定排序的比较器，当用Iterator 遍历TreeMap时，得到的记录是排过序的。

一般情况下，我们用的最多的是HashMap,HashMap里面存入的键值对在取出的时候是随机的,它根据键的HashCode值存储数据,根据键可以直接获取它的值，具有很快的访问速度。

在Map 中插入、删除和定位元素，HashMap 是最好的选择。

TreeMap取出来的是排序后的键值对。

但如果您要按自然顺序或自定义顺序遍历键，那么TreeMap会更好。

LinkedHashMap 是HashMap的一个子类，如果需要输出的顺序和输入的相同,那么用LinkedHashMap可以实现,它还可以按读取顺序来排列，像连接池中可以应用。

红黑树的红色内结点个数的最小值和最大值

刚写过红黑树的应用。

但却是没想过红节点的数量。

感觉红节点可能最少完全一个都没有的0个， 到最多一半节点数量5000/2 对于n个节点中的红色节点数，最小值0，最大值“n整除2”

红黑树能不能节点全黑？

在进行红黑树的构造的时候，为了满足第5点，则必须每次插入的节点颜色预设为红色，插入后，有可能会导致2、4不满足，然后进行节点调整。

所以如果是构造出来的，一般来说，不会有节点全黑的红黑树

红黑树的java实现？

public class TreeNode { public int data; public String color; public TreeNode lchild; public TreeNode rchild; } 2.RBTree.JAVA package 第13章_红黑树; /** * @author greatwqs * @date 2009.9.12 * */ public class RBTree { TreeNode root; // 建立红黑树 public void create(int[] list) { for (int i = 0; i < list.length; i++) { this.insert(list[i]); } } // 插入一个元素 public void insert(int elem) {// 为新元素开辟一个空间 TreeNode s = new TreeNode(); s.data = elem; s.color = "black"; s.lchild = null; s.rchild = null; // 判断根是否为空,如果为空,则将root指向新元素.否则,进入循环 if (root == null) { root = s; root.color = "red"; return; } else { // 定义四个指针,分别指向祖先,祖,父,自身 TreeNode p = root, q; TreeNode parent = root; TreeNode grand = root; TreeNode ancestor = root; while (p != null) { // 如果P的左右孩子均不为空且颜色均为红色,则执行颜色转换并进行调整 if (p.lchild != null && p.rchild != null) { if (p.lchild.color == ("black") && p.rchild.color == ("black")) { convertColor(p); adjust(ancestor, grand, parent, p); } } if (elem == p.data) { return; } q = p; // 指针依次向后移动 ancestor = grand; grand = parent; parent = p; // 如果,元素小于P if (elem < q.data) { // P的左孩子为空 if (q.lchild == null) { // 将P的左孩子指向新建元素 q.lchild = s; p = s; // 调整 adjust(ancestor, grand, parent, p); return; } else {// P的左孩子不为空 // P向左下移动 p = p.lchild; } } else {// 如果,元素大于P if (elem > q.data) { // P的右孩子为空 if (q.rchild == null) { // 将P的右孩子指向新建元素 q.rchild = s; p = s;// 调整 adjust(ancestor, grand, parent, p); return; } else {// P的右孩子不为空 // P向右下移动 p = p.rchild; } } } } } } // 调整颜色的方法 public void convertColor(TreeNode p) { // 将P的左右孩子的颜色均置为红 p.lchild.color = "red"; p.rchild.color = "red"; // 若P为根结点,则颜色仍为红,否则颜色置为黑 if (!(p.equals(root))) { p.color = "black"; return; } if (p.equals(root)) { p.color = "red"; } } public void adjust(TreeNode ancestor, TreeNode grand, TreeNode parent, TreeNode x) {// 是否存在黑黑冲突 if (!(parent.color == "black" && x.color == "black")) { return; } // 符合一次调整的,将调用一次调整 if ((grand.lchild == parent && parent.lchild == x) || (grand.rchild == parent && parent.rchild == x)) { onceAdjust(ancestor, grand, parent, x); return; } // 符合二次调整的,将调用二次调整 if ((grand.lchild == parent && parent.rchild == x) || (grand.rchild == parent && parent.lchild == x)) { twiceAdjust(ancestor, grand, parent, x); return; } } private void onceAdjust(TreeNode ancestor, TreeNode grand, TreeNode parent, TreeNode x) { // 调整父结点和祖结点的颜色 this.exchangeColor(grand); this.exchangeColor(parent); // 将祖先结点指向父结点 if (ancestor == grand && ancestor == this.root) { this.root = parent; ancestor = parent; } else { if (ancestor.lchild == grand) { ancestor.lchild = parent; } else if (ancestor.rchild == grand) { ancestor.rchild = parent; } } // 左左型调整 if (grand.lchild == parent && parent.lchild == x) { grand.lchild = parent.rchild; parent.rchild = grand; return; } // 右右型调整 if (grand.rchild == parent && parent.rchild == x) { grand.rchild = parent.rchild; parent.lchild = grand; return; } } private void twiceAdjust(TreeNode ancestor, TreeNode grand, TreeNode parent, TreeNode x) { // 调整自身结点和祖结点的颜色 this.exchangeColor(grand); this.exchangeColor(x); // 将祖先结点指向自身结点 if (ancestor == grand && ancestor == root) { root = x; ancestor = x; } else { if (ancestor.lchild == grand) { ancestor.lchild = x; } else if (ancestor.rchild == grand) { ancestor.rchild = x; } else if (ancestor == root) { ancestor = x; root = x; } } // 左右型调整 if (grand.lchild == parent && parent.rchild == x) { grand.lchild = x.rchild; parent.rchild = x.lchild; x.lchild = parent; x.rchild = grand; return; } // 右左型调整 if (grand.rchild == parent && parent.lchild == x) { grand.rchild = x.lchild; parent.lchild = x.rchild; x.lchild = grand; x.rchild = parent; return; } } // 变换颜色的方法 private void exchangeColor(TreeNode p) { if (p.color.equals("black")) { p.color = "red"; } else { p.color = "black"; } } public void inorder() { inorder(root); } // 中序遍历 private void inorder(TreeNode root) { if (root != null) { inorder(root.lchild); System.out.println(root.data + " " + root.color); inorder(root.rchild); } } } 3.RBTreeTest.JAVA package 第13章_红黑树; import java.util.Random; import java.util.Scanner; /** * @author greatwqs * @date 2009.9.12 * */ public class RBTreeTest { /** * @param args */ public static void main(String[] args) { RBTree rbt = new RBTree(); Scanner wqs = new Scanner(System.in); Random rand = new Random(); System.out.println("请输入建立红黑树的元素数目:"); int TotalNum = wqs.nextInt(); int[] list = new int[TotalNum]; System.out.println("创建红黑树随机元素值如下:"); for(int i = 0; i < list.length; i++){ list[i] = Math.abs(rand.nextInt()) % 100; System.out.println(list[i]); } rbt.create(list); System.out.println("红黑树建立之后输出:"); rbt.inorder(); } } ======================= 运行结果如下(具体从大到小排序,见二叉查找树,相似算法): =========================== 请输入建立红黑树的元素数目: 8 创建红黑树随机元素值如下: 30 34 52 61 48 36 53 73 红黑树建立之后输出: 30 red 36 black 48 red 52 black 53 black 61 red 73 black 34 red 36 black 48 red 52 black 53 black 61 red 73 black