树

二叉排序树的平均查找长度是O(log2n),二叉排序树的查找效率与二叉树的树形有关,
完全二叉树的查找效率最高

二叉树的节点总数n=n0+n1+n2
对于一个非空二叉树，有以下等式成立 n0=n2+1
完全二叉树
当节点数N为奇数，说明n1为0，说明该树结构中没有度为1的节点。n=n0+n2 ----->> n=n0+n0-1
当节点数为偶数时，说明有一个度为1的节点n=n0+n1+n2 ----->>n=n0+1+n0-1

解决哈希冲突的链地址算法中，关于插入新的数据项的时间表述正确的是（ ）
A. 和数组已占用单元的百分比成正比
B. 和链表数目成正比
C. 和哈希表中项数成正比
D. 随装填因子线性增长
参考答案：D

可唯一确定一棵二叉树的是:
给定一棵二叉树的后序和中序遍历序列
给定一棵二叉树的先序和中序遍历序列
https://blog.csdn.net/whing123/article/details/78060427
具有2018个节点完全二叉树, 叶子节点数为()个, 高度为()
(1) 1009
(2) 11
具有n个节点的完全二叉树的深度为log2(n) + 1

二叉树有8个度为1的节点，3个叶子节点 总共有几个节点。
应该是3+2+8=13

树的遍历tree traversal

广度优先BFS
深度优先DFS

https://img-blog.csdnimg.cn/20191212213732867.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzYyNjc3,size_16,color_FFFFFF,t_70

红黑树

时间复杂度 : O(lgn)
（Red Black Tree）
红黑树是自平衡二叉查找树，我们知道，二叉查找树这一数据结构并不难，而红黑树之所以难是难在它是自平衡的二叉查找树，在进行插入和删除等可能会破坏树的平衡的操作时，需要重新自处理达到平衡状态。

红黑树性质

  • 性质1：每个节点要么是黑色，要么是红色。根节点是黑色。叶子节点（NIL）是黑色。
  • 性质2：父子不能同时为红色
  • 性质3：每个红色结点的两个子结点一定都是黑色。
  • 性质4：任意一结点到每个叶子结点的路径都包含数量相同的黑结点。

AVL树

AVL树是带有平衡条件的二叉查找树,一般是用平衡因子差值判断是否平衡并通过旋转来实现平衡,左右子树树高不超过1,和红黑树相比,它是严格的平衡二叉树,平衡条件必须满足(所有节点的左右子树高度差不超过1).不管我们是执行插入还是删除操作,只要不满足上面的条件,就要通过旋转来保持平衡,而旋转是非常耗时的
AVL树适合用于插入删除次数比较少，但查找多的情况。

散列表

散列表的装填因子定义为：α=填入表中的元素个数/散列表的长度

α是散列表装满程度的标志因子。由于表长是定值，α与“填入表中的元素个数”成正比，所以，α越大，填入表中的元素较多，产生冲突的可能性就越大；α越小，填入表中的元素较少，产生冲突的可能性就越小。

堆

下列各序列中不是堆的是（ ）
A. (9,8,5,3,4,2,1)
B. (9,4,5,8,3,1,2)<
C. (9,5,8,4,3,2,1)
D. (9,8,5,4,3,1,2)
解析：堆要求父节点的元素值必须全部大于或者小于子节点的元素值，A、C和D都是符合条件的大根堆，B的第三层的元素8大于第二层的父元素值4，不符合堆的条件，故而本题答案为B选项。