进阶二叉树

目录

二叉树

二叉搜索树

二叉搜索树的定义

二叉搜索树的操作 

哈夫曼树

哈夫曼树的定义

哈夫曼树的构造

哈夫曼树的性质

 平衡二叉树

平衡二叉树的定义：

平衡二叉树的插入调整

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，则从根结点到第L层结点的路径长度为L-1。

 

哈夫曼树的构造

每次把权值最小的两棵二叉树合并，合并得到一个新的结点，其权值是合并的两个结点的权值之和。

哈夫曼树的性质

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的右子树。