进阶二叉树
目录
二叉树
二叉搜索树
二叉搜索树的定义
二叉搜索树的操作
哈夫曼树
哈夫曼树的定义
哈夫曼树的构造
哈夫曼树的性质
平衡二叉树
平衡二叉树的定义：
平衡二叉树的插入调整
1.LL插入/LL旋转
2.RR插入/RR旋转
3.LR插入/LR旋转
4.RL插入/RL旋转
二叉树
二叉搜索树
二叉搜索树的定义
二叉搜索树也称二叉排序树或二叉查找树，树上任何一个结点的值，比起其左子树的值都要大，比其右子树的值都要小，并且其左右子树都是二叉搜索树
二叉搜索树的操作
1.插入：同上一篇二叉树的插入一样，插入值为x的结点
2.删除：分为三种情况：
（1）删除的结点没有子结点，就将删除的结点的父节点指向NULL
（2）删除的结点有一个子结点，就将删除的结点的父节点指向删除结点的子节点
（3）删除的节点有两个子节点，就将左子树最大的结点或右子树最小的结点替换删除的·结点
3.查找：
在树中查找值为x的结点，并返回其所在位置的地址
二叉搜索树：
最大元素一定在最右分支的端结点上
最小元素一定在最左分支的端结点上
哈夫曼树
哈夫曼树的定义
给定n个权值作为n个叶子结点，构造一颗二叉树，若该树的带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(Huffman Tree)。哈夫曼树是带权路径长度最短的树，权值较大的结点离根较近。
带权路径长度(WPL)：设二叉树有n个叶子结点，每个叶子结点带有权值
，从根结点到每个叶子结点的长度为
则每个叶子结点的带权路径长度之和就是：
哈夫曼树的构造
每次把权值最小的两棵二叉树合并，合并得到一个新的结点，其权值是合并的两个结点的权值之和。
哈夫曼树的性质
1.没有度为1的结点
2.哈夫曼树的任意非叶结点互换后，任然是哈夫曼树
3.同一权值可能存在不同构造的哈夫曼树
平衡二叉树
平衡二叉树的定义：
平衡二叉树又被称做AVL树
任何一棵不空的平衡二叉树，其任意一结点的左右子树的高度差不能超过1，左右子树的高度差也被称做平衡因子（BF），BF（T）=hL-hR,hL和hR分别代表T树的左右子树高度，|BF(T)|<=1
不同的结点插入顺序，会导致生成不一样的树。则树的深度和平均查找长度ASL也会不同。
ASL = (同一层结点数量 * 结点的层次) / 结点总数
构成平衡二叉树所需的最少结点数：。
表示高度为h的平衡二叉树的最少结点数，等于前两层最少节点数之和再加1。其中n1=1,n2=2(n>=1)。
平衡二叉树的插入调整
插入的结点被称为“麻烦结点/破坏结点”。
一个结点其子树被插入新结点，该节点被陈称为“发现者/被破坏者”。
1.LL插入/LL旋转
插入的“破坏节点”，在“被破坏节点”的左子树的左子树上，因而叫LL插入。需要LL旋转（左单旋）。
LL旋转：被破坏结点为A，被破坏结点的右子树记为，被破坏结点的左子树的根节点为B，B的左、右子树记为、。将B结点提升为新的根节点，A作为B结点的右儿子，还作为A结点的右子树；还作为B结点的左子树；变为A结点的左子树。
2.RR插入/RR旋转
插入的“破坏节点”，在“被破坏节点”的右子树的右子树上，因而叫RR插入。需要RR旋转（右单旋）。
RR旋转：被破坏结点为A，被破坏结点的左子树记为，被破坏结点的右子树的根节点为B，B的左、右子树记为、。将B结点提升为新的根节点，A作为B结点的左儿子，还作为A结点的左子树；还作为B结点的右子树；变为A结点的右子树。
3.LR插入/LR旋转
插入的“破坏节点”，在“被破坏节点”的左子树的右子树上，因而叫LR插入。需要LR旋转。
LR旋转：被破坏节点为A，A的左子树的根节点为B，A的右子树为；B的左子树为，B的右子树的根节点为C；C的左、右子树记为、。将C结点提升为新的根节点，B作为C结点的左儿子，A作为C的右儿子；还作为B的左子树，作为B的右子树；作为A的左子树，还作为A的右子树。
4.RL插入/RL旋转
插入的“破坏节点”，在“被破坏节点”的右子树的左子树上，因而叫RL插入。需要RL旋转。
RL旋转： 被破坏节点为A，A的左子树为，A的右子树为的根节点为B；B的左子树的根节点为C，B的右子树为；C的左、右子树记为、。将C结点提升为新的根节点，A作为C结点的左儿子，B作为C的右儿子；还作为A的左子树，作为A的右子树；作为B的左子树，还作为B的右子树。