关于红黑树的节点数计算公式黑高与内部节点n的公式：n大于等于2^（h/2）-1的问题？

来源：蜘蛛抓取(WebSpider) 时间：2022-10-11 13:28 标签： 树的节点数计算公式

平衡查找树中的2-3树以及其实现红黑树。2-3树中，一个节点最多有2个key，而红黑树则使用染色的方式来标识这两个key。B树，概括来说是一个节点可以拥有多于2个子节点的二叉查找树。与自平衡二叉查找树不同，B树为系统最优化大块数据的读和写操作。B-tree算法减少定位记录时所经历的中间过程，从而加快存取速度。普遍运用在数据库和文件系统。

所以B树其实是对2-3树的扩展

B+树是对B树的变形：

  • 由于B+树在内部节点上不好含数据信息，因此在内存页中能够存放更多的key。 数据存放的更加紧密，具有更好的空间局部性。因此访问叶子几点上关联的数据也具有更好的缓存命中率。
  • B+树的叶子结点都是相链的，因此对整棵树的便利只需要一次线性遍历叶子结点即可。而且由于数据顺序排列并且相连，所以便于区间查找和搜索。而B树则需要进行每一层的递归遍历。相邻的元素可能在内存中不相邻，所以缓存命中性没有B+树好。

　　但是B树也有优点，其优点在于，由于B树的每一个节点都包含key和value，因此经常访问的元素可能离根节点更近，因此访问也更迅速。

B/B+树常用于文件系统和数据库系统中，它通过对每个节点存储个数的扩展，使得对连续的数据能够进行较快的定位和访问，能够有效减少查找时间，提高存储的空间局部性从而减少IO操作。它广泛用于文件系统及数据库中，如：

　　二叉查找树平均查找性能不错，为O(logn)，但是最坏情况会退化为O(n)。在二叉查找树的基础上进行优化，我们可以使用平衡查找树。平衡查找树中的2-3查找树，这种数据结构在插入之后能够进行自平衡操作，从而保证了树的高度在一定的范围内进而能够保证最坏情况下的时间复杂度。但是2-3查找树实现起来比较困难，红黑树是2-3树的一种简单高效的实现，他巧妙地使用颜色标记来替代2-3树中比较难处理的3-node节点问题。红黑树是一种比较高效的平衡查找树，应用非常广泛，很多编程语言的内部实现都或多或少的采用了红黑树。

　　除此之外，2-3查找树的另一个扩展——B/B+平衡树，在文件系统和数据库系统中有着广泛的应用。

6. 分块查找：分块查找又称索引顺序查找，它是顺序查找的一种改进方法。

7. 哈希查找：散列查找（直接定址），哈希函数构造方法（尽量减少冲突）+解决冲突的方法（开放定址和拉链法）

以空间换时间，map的本质就是Hash表

字符串匹配算法：KMP（从O（mn）降低到O（m+n））

　　道理其实很简单，如果目标串和模式串的字符匹配，那么就同时移动两者的下标；如果不能匹配，就使用next数组来获得移动的数目。但编程方法实现的话，next数组我们需要再修改一下，这样就能够直接获得当前失配位置应当对应的新的模式串字符下标（因为我们关注的是在失配字符之前有几个匹配的字符）。

所以，next数组来对每个位置找到最长公共前缀

适合主串和子串有很多部分匹配的情况

大致求next数组的代码：注意这里是设置最开始是-1和0，也可以设置0，1

Java中平时用的最多的Map集合就是HashMap了，它是线程不安全的。

1、当用在方法内的局部变量时，局部变量属于当前线程级别的变量，其他线程访问不了，所以这时也不存在线程安全不安全的问题了。

2、当用在单例对象成员变量的时候呢？这时候多个线程过来访问的就是同一个HashMap了，对同个HashMap操作这时候就存在线程安全的问题了。

为了避免出现场景2的线程安全的问题，不能使用HashMap作为成员变量，要寻求使用线程安全的Map，下面来总结下有哪些线程安全的Map呢？

HashTable的get/put方法都被synchronized关键字修饰，说明它们是方法级别阻塞的，它们占用共享资源锁，所以导致同时只能一个线程操作get或者put，而且get/put操作不能同时执行，所以这种同步的集合效率非常低，一般不建议使用这个集合。

这种是直接使用工具类里面的方法创建SynchronizedMap，把传入进行的HashMap对象进行了包装同步而已，来看看它的源码。

这个同步方式实现也比较简单，看出SynchronizedMap的实现方式是加了个对象锁，每次对HashMap的操作都要先获取这个mutex的对象锁才能进入，所以性能也不会比HashTable好到哪里去，也不建议使用。

这个也是最推荐使用的线程安全的Map，也是实现方式最复杂的一个集合，每个版本的实现方式也不一样，在jdk8之前是使用分段加锁的一个方式，分成16个桶，每次只加锁其中一个桶，而在jdk8又加入了红黑树和CAS算法来实现。

虽然实现起来很复杂，但使用起来也是非常简单的，在java面试中问的频率也非常高，最重要的是性能要比上面两种同步方式要快太多，推荐使用。

　　2. 迭代器型别使用范例：

　　4. Vector 的内部存储方式为数组，随机访问迭代器。

　　9. List内部存储方式是环状双链表，双向迭代器。

　　12. Deque的存储结构：双层Map，随机访问迭代器

　　16. Map的内部存储结构为红黑树

　　17. Map的size获取方式（每次对红黑树增删操作都会更新数量）:

　　18. Map的empty判断方式（每次对红黑树增删操作都会更新数量）：

　　19. Hashtable有三种方法解决碰撞：线性探测，二次探测，开链发。STL中使用的是开链法。

　　20. Hashtable的迭代器类型为前向迭代器

　　21. Hashtable的获取size方法为每次对容器的增删都更新一个临时变量。

我要回帖

更多关于 树的节点数计算公式 的文章

 

随机推荐