平衡二叉树AVL、哈夫曼树
完全不知道写的什么东西
定义
首先，平衡二叉树也是二叉排序树(搜索树) 其次，AVL树的任何一个结点，左右子树的高度差的绝对值不超过1。 平衡二叉树可以是是空树
平衡二叉树的插入
平衡二叉树的插入同二叉排序树，不同的是，平衡二叉树在插入后，如果导致树内某个结点的平衡因子绝对值大于1，则需要做相应调整，使之恢复平衡。 我们需要找到离插入结点最近的失衡结点A，在以A为根的子树上，在保持排序特性的情况下，进行调整。
具体失衡分为四种情况：
1.LL（右旋）：A的左子B的左子树上插入节点导致A失衡。
调整：直接让左子B代替A，A称为B的右子，同时让BR成为A的左子。
2.RR（左旋）：A的右子B的右子树上插入节点导致A失衡。 调整：直接让A的右子B代替A，A称为B的左子，同时让BL成为A的左子。
3.LR（先左后右）：A左子的右子树上插入结点导致A失衡。 调整： 先左旋，让E替代B，再右旋，让E替代A。 右子树的根节点E替代A，B/A分别为E的左子/右子。 4.RL（先右再左）：A右子的左子树上插入结点导致A失衡。 调整：先右旋，让D替代C，再左旋让D替代A。 将左子树的根节点D代替A，A/C分别成为其左/右子树。
考研向
因为平衡二叉树AVL基本不会出算法题，基本都是以性质为主. 1.在已知平衡树内插入结点，求新的平衡二叉树。
1.四种变换
主要考四种变换，四种变化的核心是失衡点A，及其与插入点间的祖先B，C该如何替换A——LL，RR让B替换A，LR，RL让C替换A。 子树分配：去替换的那个结点左右子树分配给未替换的两个。
如LL中，B替换A，B的BR就得给A,而A，C原本的AR,CL,CR不需要动
2.AVL的最少结点
h层平衡二叉树的最少结点数： n h = 1 + n h − 1 + n h − 2 n_h=1+n_{h-1}+n_{h-2} nh=1+nh−1+nh−2 其中 n 0 = 0 , n 1 = 1 , n 2 = 2 n_0=0,n_1=1,n_2=2 n0=0,n1=1,n2=2 所有非叶子结点平衡因子均为1 ⟶ longrightarrow ⟶ 最少结点
5层AVL最少：12个结点 6层AVL最少：20个结点
3.删除再插入
平衡树 叶/非叶 ⟶ longrightarrow ⟶ 删除再插入之后，均可能不同 or 相同！
平衡二叉树 ⟶ longrightarrow ⟶ 一切皆有可能 实例： 叶——不同
1 去0 2 加0 2
/ / /
0 2 1 3 1 3
/
3 0
非叶——相同
2 去2 3 加2 2
/ / (2替代3) /
1 3 1 1 3
非叶——不同
1 去2 1 加2 1
/ / /
0 2 0 3 0 3
/
3 2
huffman树
A的带权路径长度：根到A的路径长度(经过的边数) × imes ×A权值 树的带权路径长度(WPL)：所有叶子带权路径长度之和 W P L = ∑ i = 1 n w i l i WPL=sum_{i=1}^nw_il_i WPL=i=1∑nwili定义：在含有n个叶结点的二叉树中，WPL最小的二叉树就叫huffman树。
构造：
- 将n棵结点，分别作为只含一个结点的树，构成森林F。
- 构造一个新结点，从F中选取根结点权值最小的两个树作为新结点的左右子树，新结点的权值为左右子树根结点权值之和，
- 从F中删除刚刚选出的两个树，并将新树加入进去
- 重复2，3直至只剩下一棵树，即huffman树。
每个初始结点最后都成为了叶结点 并且huffman树中只有度为0、2 的结点，没有度为1的结点。 n 0 = n 2 + 1 n_0=n_2+1 n0=n2+1 所以 n n n个叶结点 ⟶ longrightarrow ⟶ 2 n − 1 2n-1 2n−1个结点
