为什么用红黑树,任意四个自然数中,必存在两个数,他们的差是3的倍数。为什么,用抽屉原理解答。
任意四个自然数中,必存在两个数,他们的差是3的倍数。为什么,用抽屉原理解答。
红黑树,b+树分别用于什么场景,为什么
结果是这个树大致上是平衡的。
因为操作比如插入、删除和查找某个值的最坏情况时间都要求与树的高度成比例，这个在高度上的理论上限允许红黑树在最坏情况下都是高效的，而不同于普通的二叉查找树。
空间使用率高于B+树。
红黑树：在平衡二叉树（所有节点的左右子树高度不超过1）的基础上，在每个节点增加一个存储位用来表示红或者黑。
通过对任何一条从根到叶子的路径上各个节点着色方案的限制。
基础类：二叉搜索（排序）树，线索二叉树，哈夫曼树（最优二叉树），二叉堆平衡树类：AVL，红黑树，2-3树，2-3-4树，B树，B+树，B-树，treap，SBT。
红黑树（RedBlackTree）是一种自平衡二叉查找树，是在计算机科学中用到的一种数据结构，典型的用途是实现关联数组。
红黑树是在1972年由RudolfBayer发明的，当时被称为平衡二叉B树（symmetricbinaryB-trees）。
任意四个自然数中,必存在两个数,他们的差是3的倍数。为什么,用抽屉原理解答。
一个数除以3的余数有0 1 2三种情况，将其看成3个抽屉。
。
。
。
任意四个自然数要放进这3个抽屉里面，至少有两个自然数要被放在同一个抽屉里。
。
。
同一个抽屉的两个自然数之差必是3的倍数。
。
。
。
因为他们除以3的余数相同，相减之后余数都消掉。
。
。
，所以差除以3的余数肯定是0，即是3的倍数
为什么HashMap使用红黑树而不使用AVL树?
红黑树适用于大量插入和删除；因为它是非严格的平衡树；只要从根节点到叶子节点的最长路径不超过最短路径的2倍，就不进行平衡调节
AVL树是严格的平衡树，上述的最短路径与最长路径的差不能超过|1|，AVL允许的差值小；在进行大量插入和删除操作时，频繁地进行平衡调整会严重降低效率；
红黑树虽然不是严格的平衡树，但是其依旧是平衡树；查找效率是logn；
AVL也是logn；
红黑树舍去了严格的平衡，使其插入，删除，查找的效率稳定在O(logn)
反观AVL树，查找没问题O(logn)，但是为了保证高度平衡，动态插入和删除的代价也随之增加，综合效率肯定达不到O(logn)
所以在进行大量插入，删除操作时，红黑树更优一些
Hashmap用到数据结构有
数组，链表，红黑树
在没有地址冲突时，效率O(1)
有少量地址冲突，在冲突的地址拉链(建链表)，效率在O(1)~O(logn)之间
有大量地址冲突，在冲突的地址建红黑树，效率O(logn)
