<hr> <div id="div1"><h3> <font color=red > 树 ： 二叉树，B树 </font><h3></div> 二叉树：即每个结点都最多只有两个子结点的树 完全二叉树： 叶节点只能出现在最下层和次下层，并且最下面一层的结点都集中在该层最左边的若干位置的二叉树 满二叉树：指深度为k且有2^k-1个结点的二叉树 ==二叉查找树== ： 左子树的节点值比父节点小，而右子树的节点值比父节点大 二分查找： n 个节点的二叉查找树，查找的时间复杂度为 O（logn），退化为一条链表，时间复杂度变成了 O(n) ==平衡二叉树==： 左子树的节点值比父节点小，而右子树的节点值比父节点大； **每个节点的左子树和右子树的高度差至多等于1。** ？？？ 平衡树如何构建、插入、删除、左旋、右旋等操作 ==红黑树==  红黑树的特性: （5）从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。 确保没有一条路径会比其他路径长出俩倍。因而，红黑树是相对是接近平衡的二叉树 保证平衡性的最大的目的就是降低树的高度，因为树的查找性能取决于树的高度。所以树的高度越低搜索的效率越高！ java中使用到红黑树的有TreeSet和JDK1.8的HashMap ==B树==  中序遍历为页面2->页面1->页面3->页面1->页面4。可以发现位于页面1的结点会被多次访问，且位于该结点的元素也会被多次遍历 在==B+树==中， 出现在分支结点中的元素会被当作它们在该分支结点位置的中序后继者（叶子结点）中再次列出， 每一个叶子结点都会保存一个指向后一叶子结点的指针  任何非叶子结点都会在叶结点上再次出现一次，并且所有叶子结点从左到右链接了起来 第一就是查找元素时，即使在非叶子结点找到了目标值，它也只是用来索引的，还需要继续找到它在叶子结点的位置。只需要找到范围的最小值所在位置，然后沿链表遍历即可 第二就是如果要遍历，只需要遍历一次叶子结点即可。 - B树与B+树对比 B树的优点在于数据存储在每个结点中，可以更快访问到，而不必须走到叶子结点，B树更多的用在文件系统中。 B+树的每个非叶子结点都只充当索引，所以查询必须到叶子结点结束，但它十分适合“扫库”和区间查找，而且因为大多结点只用于索引，所以并不会存储真正的数据，在内存上会更紧凑，相同的内存就可以存放更多的索引数据了。 ==B*树==：在B+树基础上，为非叶子结点也增加链表指针，将结点的最低利用率 <hr> <div id="div1"><h3> <font color=red > 线性表 ：单链表、双向链表、循环链表和双向循环链表 </font><h3></div>