‘壹’ 删除二叉查找树BST中某一特定范围中的所有元素
一开始检查该树的根节点是否在删除范围内,如果在则检查它的左子树和右子树,对于左子树而言,如果根节点还在范围内,删除该左子树跟节点以及它的右子树,继续向左检查,直到子树的跟节点不再范围内为止,然后子树向下和它的右子树检查,如果右子树跟在范围内,则删除右子树跟和它的右子树,然后子树的右子树连接到它原始右子树的左子树,直到为跟节点为止,对于该树的右子树而言,只需使用同样方法反过来即可,最后全部子树处理好了之后,对跟节点进行处理,只需删除根节点然后重新建立二叉查找树,这个方法的时间复杂度是O(h),其中h代表树的高度
‘贰’ 二叉搜索树和最优二叉搜索树的时间复杂度各是多少
二叉查找树(BST,Binary Search Tree) ,又名二叉搜索树或二叉检索树,是一颗满足如下条件的树:
1、每个节点包含一个键值
2、每个节点有最多两个孩子
3、对于任意两个节点x和y,它们满足下述搜索性质:
a、如果y在x的左子树里,则key[y] <= key[x]
b、如果y在x的右子树里,则key[y] >= key[x]
最优二叉查找树(Optimal BST,Optimal Binary Search Tree)
最优二叉查找树是使查找各节点平均代价最低的二叉查找树。具体来说就是:给定键值序列 K = <k1 , k2 , . . . , kn >,k1 < k2 <· · · < kn ,其中键值ki ,被查找的概率为pi ,要求以这些键值构建一颗二叉查找树T,使得查找的期望代价最低(查找代价为检查的节点数)。
下面是对于查找期望代价的解释:
对于键值ki , 如果其在构造的二叉查找树里的深度(离开树根的分支数)为depthT(ki ),则搜索该键值的代价= depthT(ki ) +1(需要加上深度为0的树根节点)。由于每个键值被查找的概率分别为pi ,i=1,2,3…,n。所以查找期望代价为:
E[T的查找代价] = ∑i=1~n (depthT(ki ) +1) · pi
时间复杂度
1、穷举
穷举构造最优二叉查找树,其实就是这样的一个问题:
给一个拥有n个数的已排序的节点,可以将其构造成多少种不同的BST(用来找到一个最优的二叉查找树)?
设可以构造成T(n)个,那么枚举每一个元素作为根节点的情况,当第一个元素作为根节点时,其余n-1个构成右子树,无左子树,是n-1情况时的子问题, 共T(n-1)种;当第二个元素作为根节点时,左子树有1个元素,右子树有n-2个元素,根据乘法原理共有T(1)T(n-2)种情况……依此类推得 到:T(n) = T(0)T(n-1) + T(1)T(n-2) + T(2)T(n-3) + ...... + T(n-2)T(1) + T(n-1)T(0);此外,有T(0)=T(1)=1。
下面来求解T(n):
定义函数 f(x) = T(0) + T(1) · x + T(2) · x2 + ......
那么有:
f(x)2 = (T(0)2 ) + (T(0)T(1) + T(1)T(0)) · x + (T(0)T(2) + T(1)T(1) + T(2)T(0)) · x2 + ......
= T(1) + T(2) · x + T(3) · x2 + ......
= (f(x) - T(0)) / x
= (f(x) - 1) / x
这样解方程得到 f(x) = [1 - (1 - 4x)1/2 ] / 2x
右边进行泰勒展开,再与定义式比较最终得到: T(n) = (2n)! / (n!(n+1)!)
然后根据Stirling公式:n! ~ (2πn)1/2 · (n/e)n
于是有(2n)! / n!(n+1)! ~ (4n1/2 · 2n2n ) / (2n1/2 · nn · (2(n+1))1/2 · (n+1)n )
~ 4n · (n+1)-3/2 · (n/(n+1))n
~ 4n · n-3/2
因此最后得到穷举方法构造最优二叉查找树的时间复杂度: T(n) = O(4n · n-3/2 )
2、递归
实际上左右子树是互不影响的,不需要穷举所有左右子树的组合,所以不需要用乘法原理,加法原理就可以了,这样式子变为:
T(n) = T(0) + T(n-1) + T(1) + T(n-2) + T(2) + T(n-3) + ...... + T(n-2) + T(1) + T(n-1) + T(0)
= 2(T(0) + T(1) + T(2) + ...... + T(n-1))
= 3T(n-1)
所以得到T(n) = O(3n ) ,还是指数级的一个算法
3、动态规划
上面得到指数级算法的原因在于,计算了很多重复的子树情况,一些子树的查找代价被计算了很多遍;而一棵树如果是最优二叉搜索树,那么要么它是空树,要么它 的左、右子树也是最优二叉搜索树,因此只需要将子树的查找代价记录下来,采用记忆化搜索或者是自底向上的动态规划的方法,虽然需要消耗一定的空间,但可以 把时间复杂度从指数级降到多项式级,这些空间消耗也是可以接受的。
以下是采用自底向上的解法:
输入:键值序列 K = <k1 , k2 , . . . , kn >,概率序列 P = <p1 , p2 , . . . , pn >
输出:两个二维数组,Price[i][j]表示ki 到kj 构成的最优子树的查找代价,Root[i][j]表示表示ki 到kj 构成的最优子树的根节点位置(用于重构最优二叉查找树)
算法1 :
For 子树大小size = 1 to n
For 子树的起点start = 1 to (n - size + 1) //这样子树的终点即为 end = start + size - 1,长度为size
For 该子树的所有节点作为根节点root = start to end
对于每个root,根据之前计算过的Price数组得到左右最优子树的代价,可直接得到该子树的代价price为:
左右子树的最优子树代价之和 + 所有节点的访问概率之和(因为所有节点都下降了一层)
在内层循环中找到代价最小的price和root分别记录在Price[start][end]和Root[start][end]中
下面分析这个算法的时间复杂度:
由于除了计算出我们最后需要得到的Price和Root二维数组,还产生了部分冗余的子树,因此不能简单的将算法归结为O(n2 )的算法。
对于子树大小为1时,我们考察了n个子树;
对于子树大小为2时,一共产生了(n - 1)个最优子树,但是在我们的每次考察中,都将子树的所有节点作为根节点考虑过一次,因此每得到1个大小为2的子树,我们需要考察2个不同的子树来找到一 个代价最小的,因此最后我们实际上考察了2(n - 1)个子树;
对于子树大小为3时,类似的,我们考察了3(n - 2)个子树;
……
对于子树大小为n时,我们考察了n个子树。
最后,我们一共考察了T(n) = n + 2(n - 1) + 3(n - 2) + ...... + n个子树。
求解这个公式依然可以借用之前的方法,定义函数 f(x) = 1 + 2x + 3x2 + ...... = (1 - x)-2
这样一来 f(x)2 = T(1) + T(2) · x + T(3) · x2 + ......
再借用泰勒展开得到 T(n) = (n + 2)(n + 1)n/6 = O(n3 )
或者把所有项视为n2,则有 T(n) ≤ n2 + n2 + n2 + n2 + ...... = (n+1)n2 ≤ 2n3
把中间n/2项都视为n/4 · 3n/4的话,则有 T(n) ≥ n/2 · n/4 · 3n/4 = (3/32)n3
根据时间复杂度的定义有 T(n) = O(n3 )
下面介绍一个定理,可以借此把动态规划算法的时间复杂度进一步降到O(n2 ),详细的证明参见参考文献:
定理1 :Root[i][j-1] ≤ Root[i][j] ≤ Root[i+1][j] (Root数组定义见算法1)
也就是说,算法1的第3个For就可以不用循环子树中的所有节点了,只要循环另两个子树的根节点之间的范围就可以了。算法如下,红色的为修改的部分:
算法2 :
For 子树大小size = 1 to n
For 子树的起点start = 1 to (n - size + 1) //这样子树的终点即为 end = start + size - 1,长度为size
For 该子树的所有节点作为根节点root = Root[start][end-1] to Root[start+1][end]
对于每个root,根据之前计算过的Price数组得到左右最优子树的代价,可直接得到该子树的代价price为:
左右子树的最优子树代价之和 + 所有节点的访问概率之和(因为所有节点都下降了一层)
在内层循环中找到代价最小的price和root分别记录在Price[start][end]和Root[start][end]中
在分析该算法的时间复杂度时应注意,考察的子树是与考察的内层循环中root数量一一对应的,而当start递进时,前一个root的终点正好等于后一个root的起点(算法中的红色部分),也就是说对于固定的size来说,考察的root的范围加起来应当首位相接 而且至多刚好覆盖 所有节点,因此对于每个size,最多只考察2n个root(这里缩放了一下),因此总共最多考察了2n · n = 2n2 个子树;另一方面,Root数组中每一个值对应得到的一个最优二叉查找树,也即至少需要考察n2 个子树。因此根据定义得到 T(n) = O(n2 )
‘叁’ pascal算法问题
书上有啊!、
定义:
BST 待遍历的二叉树;
postorder 后序遍历规则;
first_node 按后序遍历规则遍历时将访问的第一个结点;
current_node 当前将要访问的结点;
next_node 根据postorder规则,在current_node之后即将访问的后继结点;
parent(node) 结点node的父结点;
lchild(node) 结点node的左孩子;
rchild(node) 结点node的右孩子。
算法步骤:
1 找到BST中以postorder方式遍历时将访问的第一个结点,即first_node;
2 令current_nodeçfirst_node;
3 查找current_node的后继结点next_node:
3.1 若current_node之父结点为空,算法结束;
3.2 若current_node为其父结点的左孩子,且其父结点无右子树,则next_nodeçparent(current_node);
3.3 若current_node为其父结点的左孩子,且其父结点有右子树,则令pçparent(current_node),于是next_node为结点p之右子树中以postorder方式遍历时将访问的第一个结点;
3.4 若current_node为其父结点之右子树,则next_nodeçparent(current_node);
4 访问current_node;
5 令current_nodeçnext_node,转到3。
满二叉树时之复杂度
不妨令满二叉树的深度为k(二叉树的层数记为i=1, 2, …, k-1),则总的结点数n=2k-1。对于一棵深度为k的满二叉树,按后序遍历规则查找第一个结点的操作步骤数为k-1。对满二叉树的第i层结点(i=1, 2, …, k-1),有2i-1个结点是其父结点的左孩子,有2i-1个结点是其父结点的右孩子。对于第i层的每个左孩子结点,需要按后序遍历规则查找其后继结点,此时父结点之右子树的深度为k-i,根据前述说明,则每个左孩子结点需要执行k-i-1次查找后继结点的操作,总的操作次数为2i-1 * (k-i-1)次。对于第i层的每个右孩子结点,其父结点即为其后继结点,因此对每个右孩子结点所需要执行的操作为1,因此第i层右孩子总的操作数为2i-1 * 1。由此,第i层总的操作数为2i-1 * (k-i-1) + 2i-1 * 1=2i-1 * (k-i)。将以上所有层累加起来即得到除根结点之外的所有层上的操作数(i=1, 2, …, k-1),不妨设为α:
α= 21-1 * (k-1) + 22-1 * (k-2) + … + 2k-2 * 1 = 20 * (k-1) + 21 * (k-2) + … + 2k-2 * 1
则有
α= 2α-α= … = 2k – k – 1
以上就是除根结点之外所有结点上的操作总数。当处理根结点时,实际上只需要做一次判断即可。于是算法总的操作次数T = α+1 = 2k – k。又由前面的假设可知n=2k-1,因此2k=n+1,k=lg(n+1)。故可得算法总的操作数为:
T = n+1-lg(n+1)
故,该算法的复杂度为O(n)。
‘肆’ 求基于BST技术的PCB测试方法
目前随着使用大规模集成电路的产品不断出现,相应的PCB的安装和测试工作已越来越困难。虽然PCB的测试仍然使用在线测试技术这一传统方法,但是这种方法由于芯片的小型化及封装而变得问题越来越多。现在一种新的测试技术——边界扫描测试技术已逐步得到发展,大多数的ASIC电路和许多中等规模的设备已开始利用边界扫描测试技术进行设计。BST技术是按照IEEE1149.1标准,提供了一套完整的测试方案。在实际的测试中,它不需要借助于复杂和昂贵的测试设备,并且提供一种独立于电路板技术的测试方法。采用边界扫描测试技术进行集成电路设计和PCB设计,其最大的优点是测试过程简单,显着地减少了生产、实验、使用和维修过程中的测试诊断时间,从而极大地降低了成本。文章引自深圳宏力捷电子!
1 BST的基本组成
BST电路按照IEEE1149.1标准构成,其中含有测试存取通道TAP及控制器、指令寄存器IR和测试数据寄存器组TDR。测试存取通道TAP是一个5芯引脚(其中l芯为复位端)的连接器。TAP控制器是一个16状态的状态机,可产生时钟信号和各种控制信号(即产生测试、移位、捕获和更新等信号),从而使指令或测试数据移入相应的寄存器,并控制边界扫描测试的各种工作状态。
1.1测试时钟输入端TCK
TCK信号允许集成电路IC的边界扫描部分与系统内的时钟同步并独立工作。
1.2测试方式选择输入端TMS
测试方式选择TMS引脚为控制信号,其决定TAP控制器的工作状态。TMS须在TCK的上升沿之前建立。
1.3测试数据输入端TDI
在测试时钟脉冲TCK的上升沿,通过TDI串入的数据移入指令寄存器或测试数据寄存器,TAP控制器决定移入的数据是指令或测试数据。
1.4测试数据输出端TDO
在测试时钟脉冲TCK的下降沿,通过TDO从指令寄存器或测试数据寄存器串出数据,TAP控制器决定串出的数据是指令或测试数据。
2 PCB的测试系统
2.1 测试系统结构
其硬件包含通用的PC机、BST测试仪和串行BST信号电缆(含有4路信号的总线,其图中数字含义如下:1为TDI、2为TCK、3为TMS、4为TDO)。测试仪通过标准并口与PC机连接,通过串行信号电缆与PCB上的测试存取口TAP相连。
假设PCB上有A、B、C三个模块,模块可以是由单个芯片或多个芯片构成的。它们是按IEEE1149.1标准设计的,即在芯片的I/O管脚处增加BS寄存器(模块中虚线经过的位置),可进行边界扫描测试。若所设计的数字系统或设备有多块PCB,可通过串行信号电缆与PCB相连。使用者可以通过编程来灵活选择需测试的芯片、模块或整个PCB。
2.2 测试系统原理
测试者可根据PCB的网表和器件模型,利用PC机软件编程自动生成检测电路故障的测试图形。PC机应有两个至少32位I/O管脚的插板,这样可形成32位读/写管脚,方便读和写操作。
测试软件应包括预处理器和执行单元。其中预处理器读出测试图形并获取这些图形可能的关系,得到的结果是一组文件,包括存储和控制信息。执行单元装入上述文件,然后执行测试。过程为先读存储信息,把数据置于输入端口,从适当的输出端口读取数据,并同预期的结果进行比较。若发现故障,将产生一个故障报告,并标明故障的位置,最后加入诊断程序,给出故障的具体位置。
2.3测试内容
·测试PCB的I/O管脚的连线。因为PCB的I/O管脚为测试仪提供了唯一的存取通道;
·测试PCB上IC芯片的完整性,在芯片的装配过程中,IC芯片或许己损坏。可采用内建自测试和内部测试,以验证芯片的好坏;
·测试PCB上IC芯片互连的开路与短路故障,可采用外部测试加以验证:
·测试PCB上总线的完整性,通过其测试可检测与总线相连的IC芯片I/O管脚是否存在开路故障。
随着BST技术的不断发展,PCB测试将逐步完善。由于可编程集成电路的大量使用,PCB测试的灵活性和适用性将会提高,而相应的测试系统的成本将会减少。设计者可以在PCB上全部采用可编程逻辑的集成电路,只要通过软件编程即可修改芯片逻辑,从而做成通用的PCB,使PCB电路板可以完成不同的功能。这样边界扫描测试技术将使得PCB测试更加方便快捷,极大地降低测试成本。
‘伍’ 数据结构问题
很久没碰树了,不知道是不是这意思。
这个是普通的二叉树么,左边的小,右边的大。
现在变成左边的大,右边的小而已,取原来根节点,把原来的节点重新插入变新树
最大的就在最左边。
/***************
定义结构体tree
****************/
typedef struct tree
{
int data;
struct tree *left;
struct tree *right;
}tree;
tree* creat_leaf(int value)
{
tree* new=(tree *)malloc(sizeof(tree));
new->data=value;
new->left=NULL;
new->right=NULL;
return new;
}
/*************
树的插入
*************/
void *insert_tree(tree* root,int value)
{
if(root != NULL)
{
if(value < root->data) //这是原来树的插入方法,改此处判断条件就可以了啊
{
root->left = (tree*)insert_tree(root->left,value);
}
else if(value > root->data)//.....
{
root->right = (tree*)insert_tree(root->right,value);
}
return root;
}
creat_leaf(value);
}
‘陆’ 二叉搜索树(BST)满足一下条件:1灭个节点包含一个键值 2每个节点最多两个孩子 3对于任意两个节点满足
您插入顺序从0 size-1个。根据该方案,始终是大于当前值。那么,到底是总是正确的。
所以你总是会产生变形正确的树枝。
前太深了,所以,当你的价值超过一定数量的堆栈溢出。
如果我说是,你的程序将永远不会崩溃的开始,但在运行,相当于在4705-4706崩溃时压入。你的程序复杂度为O(N ^ 2),所以它是缓慢的。
如果您使用的是VC,或显示当前堆栈崩溃,gdb调试器,你可以看到一个壮观的千层UIinsert。哈哈!
‘柒’ 三, 解释下列术语 1, 静态链表 2, 无向连通图 3, 排序 4, 堆栈 5, 二叉排序树
静态链表:用数组描述的链表,即称为静态链表。但是这种存储结构,仍需要预先分配一个较大的空间,但在作为线性表的插入和删除操作时不需移动元素,仅需修改指针,故仍具有链式存储结构的主要优点。
无相连通图:撤去任意一个节点的信息,求出剩下的(n-1)*(n-1)矩阵的行列式,此值即为这个无向连通图的生成树个数。复杂度为O(n^3)
排序是计算机内经常进行的一种操作,其目的是将一组“无序”的记录序列调整为“有序”的记录序列。分内部排序和外部排序。
堆栈都是一种数据项按序排列的数据结构,只能在一端(称为栈顶(top))对数据项进行插入和删除。要点:堆:顺序随意栈:后进先出。
二叉排序树(Binary Sort Tree)又称二叉查找(搜索)树(Binary Search Tree)。其定义为:二叉排序树或者是空树,或者是满足如下性质的二叉树:
①若它的左子树非空,则左子树上所有结点的值均小于根结点的值;
②若它的右子树非空,则右子树上所有结点的值均大于根结点的值;
③左、右子树本身又各是一棵二叉排序树。
上述性质简称二叉排序树性质(BST性质),故二叉排序树实际上是满足BST性质的二叉树。
‘捌’ BST是什么意思!
1、BST(贝斯特),公司原名:深圳贝斯特机械电子有限公司,成立于一九九一年,是专门从事贝斯特点钞机、点验钞机、验钞仪、票据鉴别仪、复点机、捆扎机、扎钞机、钱箱开箱钳、反假货币宣传工作站等金融机具的开发、生产、销售的中外合资企业,注册资金2600万港币。
2、二叉搜索树(BST)又称二叉查找树或二叉排序树。一棵二叉搜索树是以二叉树来组织的,可以使用一个链表数据结构来表示,其中每一个结点就是一个对象。
二叉搜索树性质
设x是二叉搜索树中的一个结点。如果y是x左子树中的一个结点,那么y.key≤x.key。如果y是x右子树中的一个结点,那么y.key≥x.key。
在二叉搜索树中:
1、若任意结点的左子树不空,则左子树上所有结点的值均不大于它的根结点的值。
2、若任意结点的右子树不空,则右子树上所有结点的值均不小于它的根结点的值。
3、任意结点的左、右子树也分别为二叉搜索树。
以上内容参考:网络-二叉搜索树、网络-BST