经典模板网站建设,wordpress portal,提供手机自适应网站制作,百度推广优化师培训目录 二叉树
二叉搜索树
二叉搜索树的定义
二叉搜索树的操作
哈夫曼树
哈夫曼树的定义
哈夫曼树的构造
哈夫曼树的性质 平衡二叉树
平衡二叉树的定义#xff1a;
平衡二叉树的插入调整
1.LL插入/LL旋转
2.RR插入/RR旋转
3.LR插入/LR旋转
4.RL插入/RL旋转 二叉树…目录 二叉树
二叉搜索树
二叉搜索树的定义
二叉搜索树的操作
哈夫曼树
哈夫曼树的定义
哈夫曼树的构造
哈夫曼树的性质 平衡二叉树
平衡二叉树的定义
平衡二叉树的插入调整
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左右子树的高度差也被称做平衡因子BFBFThL-hR,hL和hR分别代表T树的左右子树高度|BF(T)|1
不同的结点插入顺序会导致生成不一样的树。则树的深度和平均查找长度ASL也会不同。
ASL (同一层结点数量 * 结点的层次) / 结点总数
构成平衡二叉树所需的最少结点数。表示高度为h的平衡二叉树的最少结点数等于前两层最少节点数之和再加1。其中n11,n22(n1)。
平衡二叉树的插入调整
插入的结点被称为“麻烦结点/破坏结点”。
一个结点其子树被插入新结点该节点被陈称为“发现者/被破坏者”。
1.LL插入/LL旋转
插入的“破坏节点”在“被破坏节点”的左子树的左子树上因而叫LL插入。需要LL旋转左单旋。 LL旋转被破坏结点为A被破坏结点的右子树记为被破坏结点的左子树的根节点为BB的左、右子树记为、。将B结点提升为新的根节点A作为B结点的右儿子还作为A结点的右子树还作为B结点的左子树变为A结点的左子树。 2.RR插入/RR旋转
插入的“破坏节点”在“被破坏节点”的右子树的右子树上因而叫RR插入。需要RR旋转右单旋。
RR旋转被破坏结点为A被破坏结点的左子树记为被破坏结点的右子树的根节点为BB的左、右子树记为、。将B结点提升为新的根节点A作为B结点的左儿子还作为A结点的左子树还作为B结点的右子树变为A结点的右子树。
3.LR插入/LR旋转
插入的“破坏节点”在“被破坏节点”的左子树的右子树上因而叫LR插入。需要LR旋转。
LR旋转被破坏节点为AA的左子树的根节点为BA的右子树为B的左子树为B的右子树的根节点为CC的左、右子树记为、。将C结点提升为新的根节点B作为C结点的左儿子A作为C的右儿子还作为B的左子树作为B的右子树作为A的左子树还作为A的右子树。
4.RL插入/RL旋转
插入的“破坏节点”在“被破坏节点”的右子树的左子树上因而叫RL插入。需要RL旋转。
RL旋转 被破坏节点为AA的左子树为A的右子树为的根节点为BB的左子树的根节点为CB的右子树为C的左、右子树记为、。将C结点提升为新的根节点A作为C结点的左儿子B作为C的右儿子还作为A的左子树作为A的右子树作为B的左子树还作为B的右子树。
