锐客网

  1. 首页 > 睿知 > it技术 > >

红黑树的左旋java代码 红黑树csdn( 四 )

IT技术删除


当SL,SR都是红色，这种变化只通过改变颜色就可以让s变成红色，变成组合2的情况 。
当SL,SR 只有一个红色的时候，通过改变颜色是不能达到要求的 。因此我们就需要做旋转来达到要求 。
当SL SR 都是黑色 。没有红色，p结点一下是不能解决这个问题的 。那怎么办呢？这样只能依赖p的父类了 。不过这里需要注意的是p本身不平衡 ， 我们这里依赖p的父类的时候，p需要是平衡的 。如何平衡p呢？
我们只需要将s变成红色就可以了 。p就平衡了 。
不过这里注意，p的这一整支的所有分支都是少黑色结点1 的 。
这里我们注意到p只有一个儿子 。这里我们需要把p当成删除结点x的一个儿子 。这样就转换成了x带一个儿子的情况了 。这种情况如何平衡树 。下面讨论一个孩子的时候包含 ， 暂时不在这里讲解 。
先拿一种情况分析 x是p的左儿子，x有一个左儿子
分析L 如果L是黑色的话，肯定是nil 。因此可以将这种只有一个儿子的情况转换成没有儿子的情况 。也可以这么说 ， 要是x有儿子 ， 儿子的颜色一定不是黑色 。而是红色 。如图
java中哪些数据结构使用了红黑树参考资料的网页上有比较的代码,你可以仔细看下~~~
java中HashMap,LinkedHashMap,TreeMap红黑树的左旋java代码 ， HashTable的区别
java为数据结构中的映射定义了一个接口java.util.Map;它有四个实现类,分别是HashMap Hashtable LinkedHashMap 和TreeMap
Map主要用于存储健值对红黑树的左旋java代码，根据键得到值，因此不允许键重复(重复了覆盖了),但允许值重复 。
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可以实现,它还可以按读取顺序来排列，像连接池中可以应用 。
红黑树——一个自平衡的二叉搜索树 普通的二叉搜索树在最坏的情况下，可能退化成一个链表 。而又因为二叉搜索树的所有操作的性能（添加 ， 删除 ， 查找等），与二叉搜索树的高度有关 。在最坏的情况下，二叉搜索树的高度和元素个数相同，此时二叉搜索树的效率降为了O(n)级别 。

推荐阅读


上一篇：数据结构c语言版视频，数据结构c语言版视频

下一篇：耳机单反直播教程，用单反直播怎么设置