尾递归会被优化成循环，不会导致爆栈

查找

静态查找： 集合记录固定，没有插入删除操作

动态查找： 集合记录不固定，存在插入删除操作

哨兵

在数组的边界上设置一个值，使得循环条件到哨兵时必然导致循环退出，以减少循环条件判断。[[二分搜索#端点处理]]

顺序查找

时间复杂度 $O(n)$

二分查找

要求 $n$ 个数据有序，存放在满足随机访问的容器中（如数组）。

• 可查找到元素： 在上图的序列中查找 $444$

1. 首先计算出 $mid=\frac{left+right}{2}=\frac{1+13}{2}=7$
2. 因为 $444>a_7=100$，将 $left=mid+1$，此时 $mid=11$（下取整）
3. 因为 $444>a_{11}=368$，更新 $left$ 的值，计算 $mid=12$
4. 此时 $a_{mid}=444$，搜索结束

---

• 不可查找到元素：

在上图序列中找 43

1. $left=1,mid=7,a_7>44$
2. $right=mid-1=6,mid=3,a_3<44$
3. $left=mid+1=4,mid=5,a_5>43$
4. $right=mid-1=4,mid=4,a_4>43$
5. $left=4,right=mid-1=3$
6. 此时 $left=4\ge right=3$，搜索结束，找不到元素

STL 二分

默认升序序列，降序需要重载运算符。

binary_serach(arr[],arr[]+size,key);//是否找到key
lower_bound(arr[],arr[]+size,key);//返回第一个大于等于key的地址
upper_bound(arr[],arr[]+size,key);//返回第一个大于key的地址
distance(iterator a,itreator b);

通过这些函数配合，可以求出区间内符合条件的数的个数。 注意事项

1. Distance 函数有前后之分
2. 当 insert 容器后之前的迭代器会失效
3. 二分前提是一个升序（非降序）对象

二分查找判定树

树的深度决定了最坏情况下的查找次数

1. 判定树上每个节点需要的查找次数等于该节点所在的层数
2. $n$ 个节点的判定树深度为 $\lfloor lo{g}_{2}n\rfloor +1$
3. 平均查找次数 ASL = $\frac{4\times 4+4\times 3+2\times 2+1}{11}=3$

树

定义

1. 树是 $n$ 个结点构成的有限集合。
2. $n=0$，称为空树
3. 根节点用 $r$ 表示（root）
4. 其余节点可分为 $m$ 个互不相交的有限集 $T_1..T_m$，其中每个集合都可看成原来树的子树
5. 不同子树节点之间不可相连，每个结点只有一个父节点
6. $n$ 个结点的树有 $n-1$ 条边

术语

1. 结点的子树个数称之为度
2. 树的所有节点中最大的度数称之为树的度
3. 度为 0 的节点为叶节点 ^ae90eb
4. 有子树的节点为子树的父节点
5. 若 A 节点是 B 节点的父节点，则 B 是 A 的子节点
6. 具有同一父节点的为兄弟节点
7. 从 $n_1$ 到 $n_i$ 的边的个数称之为路径长度
8. 从树根到某一节点上的所有节点称之为这个节点的祖先节点
9. 某一节点的子树中的所有节点是这个节点的子孙节点
10. 根节点为第一层，其他任意节点是父节点的层数加 1
11. 树中所有节点的最大层次是这棵树的深度

二叉树

二叉树：儿子-兄弟表示法 表示下一层的儿子和本层的兄弟，如果没有则用表示为 N； 表示的一课树：

定义

二叉树是一个有穷的节点集合。 若不为空，由左子树 $T_L$ 和右子树 $T_R$ 两个不相交的子树构成、

特殊二叉树

斜二叉树、完美二叉树、完全二叉树、

性质

1. 第 $i$ 层的最大节点数为 $2^{i-1}，i\ge 1$，由等比求和推导，完美二叉树符合

$$S_n=\frac{1-2^n}{1-2}=2^n-1$$

2. [[树#^ae90eb]] 满足 $n_0=n_2+1$ 推导：

$$\begin{array}{c}\sum _{i=0}^2{n}_i-1=\sum _{i=0}^{2}i{n}_i\\ n_0=n_2+1\end{array}$$

抽象数据类型定义、遍历

存储

数组存储

1. 非根节点的父节点为 $\lfloor \frac{i}{2}\rfloor$
2. 第 i 层的父节点的下一层为 $2i$ 和 $2i+1$ 如果是一般二叉树，则可以补成完全二叉树再通过数组存储，但显然会造成空间浪费。

链表存储

遍历

核心问题是将二维结构线性化。

先序遍历

根节点>左子树>右子树 从根节点开始分别对左右子树做先序遍历，对每个子树都是如此。

中序遍历

左子树>根节点>右子树

后序遍历

左子树>右子树>根节点 容易发现，所谓先后就是值访问根节点的次序先后，遍历顺序相同，只不过是访问各节点数据的时机不同。

---

中序非递归遍历

这是针对完全二叉树的， 最后的结束条件是没有右子树且堆栈为空。

---

无论是堆栈和队列都是用来保存遍历过程中暂时不访问的节点。

层序遍历

一层一层向下访问即可。

[[队列]] [[2023.12.29#广度优先搜索]]

二元运算表达式树

中缀表达式会会受到运算符优先级影响，需要加括号消除。

[[堆栈#表达式求值]]

先序+中序确定二叉树

同构二叉树判断

P135 4-2.1

1. 静态链表 [[链表模拟#牛客周赛 Round 31 D]] 建树 从 0 开始编号, left 和 right 是对应节点在数组中的位置。 那么如何找到根节点呢？只需要找到数组中唯一没有被记录的节点 1，因为记的都是下一级节点，根节点自然没有父节点来记录它。
2. 程序实现
   • 读入二叉树，存进数组，并确定根节点
   • 使用前序遍历判定同构
     1. 左右空则同构
     2. 左右有一侧空则不同构
     3. 根节点不同则不同构
     4. 如果均没有左子树，就要递归判断右子树是否同构
     5. 左右非空，且左节点相同，则判定两棵树的左节点元素是否相同，判定左右是否相等
     6. 左右非空，且左节点不相同，则判断左右是否同构

二叉搜索树

AVL 树

单旋调整

左右单旋取决于破坏 AVL 平衡的节点所在的位置是被破坏的左子树还是右子树。 破坏者位于左子树的左侧或者是右子树的右侧。

双旋调整

哈夫曼树

由哈夫曼树的过构造过程可知，哈夫曼树不存在度为 1 的接非叶子结点。

集合

结构数组表示

按秩归并

先讨论未经路径压缩后的集合树。 最坏情况或许是一个艮节点正好合并了两个相等大小的集合？这时候树高 $lo{g}_{2}N$，如果每次查询叶子结点，时间复杂度 $O(NlogN)$

路径压缩

一次合并通常需要两次查找，所以 $M\ge N$ 是自然情况。 一些题中的 N 较小，路径压缩可能没有明显优势。

---

[[堆]]

建树

1. 先序+中序建树 注意中序遍历只起到辅助作用，最终划分的还是前序遍历的结果。 根据先序遍历结果确定根节点，然后由此给中序分段，再用左右子树进行递归建树。

class Solution {
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        this->preorder = preorder;
        for(int i = 0;i < inorder.size();++i){
            dic[inorder[i]] = i;//按照下标建立一个哈希表索引
        }
        return recur(0,0,inorder.size()-1);
    }
private:
    vector<int> preorder;
    unordered_map<int,int> dic;
    TreeNode* recur(int root,int left,int right){//left和right是中序遍历的边界
        if(left > right) return nullptr;
        TreeNode* node = new TreeNode(preorder[root]);//pre的第一个节点就是当前的根节点
        int index = dic[preorder[root]];
        node->left = recur(root+1,left,index-1);
        node->right = recur(index-left+1+root,index+1,right);//就是加上一个左子树的长度
        return node;
    }
};