MyException - 我的异常网
当前位置:我的异常网» 软件架构设计 » 二叉树的使用详解 - 数据结构

二叉树的使用详解 - 数据结构

www.myexceptions.net  网友分享于:2013-06-27  浏览:21次
二叉树的应用详解 - 数据结构


概述:

平衡树——特点:所有结点左右子树深度差≤1

排序树——特点:所有结点“左小右大
字典树——由字符串构成的二叉排序树
判定树——特点:分支查找树(例如12个球如何只称3次便分出轻重)
带权树——特点:路径带权值(例如长度)

最优树——是带权路径长度最短的树,又称 Huffman树,用途之一是通信中的压缩编码。

1. 二叉排序树(二叉查找树 Binary Search Tree):

1.1 二叉排序树:

或是一棵空树;或者是具有如下性质的非空二叉树:

 (1)若左子树不为空,左子树的所有结点的值均小于根的值;

 (2)若右子树不为空,右子树的所有结点均大于根的值;

 (3)它的左右子树也分别为二叉排序树。

例:二叉排序树 如图9.7:

                 



      二叉排序树的查找过程和次优二叉树类似,通常采取二叉链表作为二叉排序树的存储结构。中序遍历二叉排序树可得到一个关键字的有序序列,一个无序序列可以通过构造一棵二叉排序树变成一个有序序列,构造树的过程即为对无序序列进行排序的过程。每次插入的新的结点都是二叉排序树上新的叶子结点,在进行插入操作时,不必移动其它结点,只需改动某个结点的指针,由空变为非空即可。搜索,插入,删除的复杂度等于树高,期望O(logn),最坏O(n)(数列有序,树退化成线性表).
虽然二叉排序树的最坏效率是O(n),但它支持动态查询,且有很多改进版的二叉排序树可以使树高为O(logn),如SBT,AVL,红黑树等.故不失为一种好的动态排序方法.

2.2 二叉排序树b中查找

在二叉排序树b中查找x的过程为:

  1. 若b是空树,则搜索失败,否则:
  2. 若x等于b的根节点的数据域之值,则查找成功;否则:
  3. 若x小于b的根节点的数据域之值,则搜索左子树;否则:
  4. 查找右子树。


2.3 在二叉排序树插入结点的算法

向一个二叉排序树b中插入一个结点s的算法,过程为:

  1. 若b是空树,则将s所指结点作为根结点插入,否则:
  2. 若s->data等于b的根结点的数据域之值,则返回,否则:
  3. 若s->data小于b的根结点的数据域之值,则把s所指结点插入到左子树中,否则:
  4. 把s所指结点插入到右子树中。

2.4 在二叉排序树删除结点的算法

在二叉排序树删去一个结点,分三种情况讨论:

  1. 若*p结点为叶子结点,即PL(左子树)和PR(右子树)均为空树。由于删去叶子结点不破坏整棵树的结构,则只需修改其双亲结点的指针即可。
  2. 若*p结点只有左子树PL或右子树PR,此时只要令PL或PR直接成为其双亲结点*f的左子树即可,作此修改也不破坏二叉排序树的特性。
  3. 若*p结点的左子树和右子树均不空。在删去*p之后,为保持其它元素之间的相对位置不变,可按中序遍历保持有序进行调整,可以有两种做法:其一是令*p的左子树为*f的左子树,*s为*f左子树的最右下的结点,而*p的右子树为*s的右子树;其二是令*p的直接前驱(或直接后继)替代*p,然后再从二叉排序树中删去它的直接前驱(或直接后继)。在二叉排序树上删除一个结点的算法如下:

2. 5二叉排序树性能分析

每个结点的Ci为该结点的层次数。最坏情况下,当先后插入的关键字有序时,构成的二叉排序树蜕变为单支树,树的深度为n,其平均查找长度为 (和顺序查找相同),最好的情况是二叉排序树的形态和折半查找的判定树相同,其平均查找长度和log2(n)成正比 (O(log2(n)))。



2.6 二叉排序树的优化
    Size Balanced Tree(SBT)
    AVL树
    红黑树
    Treap(Tree+Heap)
这些均可以使查找树的高度为O(logn)

2. 平衡树二叉树(又AVL 树)

1. 1 平衡二叉树(Balanced Binary Tree)

性质:  左右子树都是平衡二叉树且所有结点左、右子树深度之差的绝对值 ≤ 1。

若定义结点的平衡因子  BF(Balance Factor) = 左子树深度 –右子树深度 则:平衡二叉树中所有结点的BF ∈[ -1, 0, 1 ]

例:判断下列二叉树是否AVL树?




常用算法有红黑树、AVL、Treap、伸展树等。在平衡二叉搜索树中,我们可以看到,其高度一般都良好地维持在O(log2n),大大降低了操作的时间复杂度。

平衡二叉树是二叉排序树的另一种形式。

我们希望由任何初始序列构成的二叉排序树都是平衡二叉树。因为平衡二叉树上任何结点的左右子树的深度之差都不超过1,则可以证明它的深度和logN是同数量级的(其中N是结点的个数)。由此,它的平均查找长度也和logN同数量级。

C语言描述:


构造二叉平衡(查找)树的方法是:在插入过程中,采用平衡旋转技术

插入算法 :

算法思想:

在平衡二叉排序树BBST上插入一个新的数据元素e的递归算法可描述如下:

1.若BBST为空树,则插入一个数据元素为e的新结点作为BBST的根结      点,树的深度增1; 

2.若e的关键字和BBST的根结点的关键字相等,则不进行插入; 

3.若e的关键字小于BBST的根结点的关键字,而且在BBST的左子树中不存在和e有相同关键字的结点,则将e插入在BBST的左子树上,并且当插入之后的左子树深度增加(+1)时,分别就下列不同情况处理之:

    iBBST的根结点的平衡因子为-1(右子树的深度大于左子树的深度):则将根结点的平衡因子更改为0BBST的深度不变;

    ii.BBST的根结点的平衡因子为0(左、右子树的深度相等):则将根结点的平衡因子更改为1,BBST的深度增1; 

    iiiBBST的根结点的平衡因子为1(左子树的深度大于右子树的深度):

         a. BBST的左子树根结点的平衡因子为1,则需进行单向右旋平衡处理,并且在右旋处理之后,将根结点和其右子树根结点的平衡因子更改为0,树的深度不变;

         b. BBST的左子树根结点的平衡因子为-1,则需进行先向左、后向右的双向旋转平衡处理,并且在旋转处理之后,修改根结点和其左、右子树根结点的平衡因子,树的                深度不变。

4.若e的关键字大于BBST的根结点的关键字,而且在BBST的右子树中不存在和e有相同关键字的结点,则将e插入在BBST的右子树上,并且当插入之后的右子树深度增加(+1)时,分别就不同情况处理之。其处理操作和上述3.中描述相对称。


3. 判定树:

      二分查找过程可用二叉树来描述:把当前查找区间的中间位置上的结点作为根,左子表和右子表中的结点分别作为根的左子树和右子树。由此得到的二叉树,称为描述二分查找的判定树(Decision Tree)或比较树(Comparison Tree)

注意:
     判定树的形态只与表结点个数n相关,而与输入实例中R[1..n].keys的取值无关。
【例】具有11个结点的有序表可用下图所示的判定树来表示。


举例:12个球如何用天平只称3次便分出轻重?

分析:12个球中必有一个非轻即重,即共有24种“次品”的可能性。每次天平称重的结果有3种,连称3次应该得到的结果有33=27种。说明仅用3次就能找出次品的可能性是存在的。

思路:首先,将12个球分三组,每组4个,任意取两组称。会有两种情况:平衡,或不平衡。其次,一定要利用已经称过的那些结论;即充分利用“旧球”的标准性作为参考。



二分查找判定树的查找
二分查找就是将给定值K与二分查找判定树的根结点的关键字进行比较。若相等,成功。否则若小于根结点的关键字,到左子树中查找。若大于根结点的关键字,则到右子树中查找。
  【例】对于有11个结点的表,若查找的结点是表中第6个结点,则只需进行一次比较;若查找的结点是表中第3或第9个结点,则需进行二次比较;找第1,4,7,10个结点需要比较三次;找到第2,5,8,11个结点需要比较四次。
     由此可见,成功的二分查找过程恰好是走了一条从判定树的根到被查结点的路径,经历比较的关键字次数恰为该结点在树中的层数。若查找失败,则其比较过程是经历了一条从判定树根到某个外部结点的路径,所需的关键字比较次数是该路径上内部结点的总数。
    【例】待查表的关键字序列为:(05,13,19,21,37,56,64,75,80,88,92),若要查找K=85的记录,所经过的内部结点为6、9、10,最后到达方形结点"9-10",其比较次数为3。
     实际上方形结点中"i-i+1"的含意为被查找值K是介于R[i].key和R[i+1].key之间的,即R[i].key<K<R[i+1].key。
二分查找的平均查找长度
      设内部结点的总数为n=2h-1,则判定树是深度为h=lg(n+1)的满二叉树(深度h不计外部结点)。树中第k层上的结点个数为2k-1,查找它们所需的比较次数是k。因此在等概率假设下,二分查找成功时的平均查找长度为:
           ASLbn≈lg(n+1)-1
  二分查找在查找失败时所需比较的关键字个数不超过判定树的深度,在最坏情况下查找成功的比较次数也不超过判定树的深度。即为:
           
  二分查找的最坏性能和平均性能相当接近。

二分查找的优点和缺点
  虽然二分查找的效率高,但是要将表按关键字排序。而排序本身是一种很费时的运算。既使采用高效率的排序方法也要花费O(nlgn)的时间。
  二分查找只适用顺序存储结构。为保持表的有序性,在顺序结构里插入和删除都必须移动大量的结点。因此,二分查找特别适用于那种一经建立就很少改动、而又经常需要查找的线性表。
  对那些查找少而又经常需要改动的线性表,可采用链表作存储结构,进行顺序查找。链表上无法实现二分查找。

5. 带权树:

即路径带有权值。例如:



6. 最优树(赫夫曼树):

赫夫曼树:给定n个权值作为n个叶子结点,构造一棵二叉树,若带权路径长度达到最小,称这样的二叉树为最优二叉树,也称为赫夫曼树(Huffman tree)。即带权路径长度最短的树。
赫夫曼树构造算法:
假设有n个权值,则构造出的哈夫曼树有n个叶子结点。 n个权值分别设为{ w1、w2、…、wn},则哈夫曼树的构造规则为:  (1) 将{w1、w2、…,wn}看成是有n 棵树的森林(每棵树仅有一个结点);  (2) 在森林中选出两个根结点的权值最小的树合并,作为一棵新树的左、右子树,且新树的根结点权值为其左、右子树根结点权值之和;  (3)从森林中删除选取的两棵树,并将新树加入森林;  (4)重复(2)、(3)步,直到森林中只剩一棵树为止,该树即为所求得的哈夫曼树。
赫夫曼编码:是通信中最经典的压缩编码.
其算法:
stdafx.h文件:
test.cpp文件:


文章评论

如何区分一个程序员是“老手“还是“新手“?
如何区分一个程序员是“老手“还是“新手“?
要嫁就嫁程序猿—钱多话少死的早
要嫁就嫁程序猿—钱多话少死的早
鲜为人知的编程真相
鲜为人知的编程真相
Java 与 .NET 的平台发展之争
Java 与 .NET 的平台发展之争
每天工作4小时的程序员
每天工作4小时的程序员
“懒”出效率是程序员的美德
“懒”出效率是程序员的美德
团队中“技术大拿”并非越多越好
团队中“技术大拿”并非越多越好
那些争议最大的编程观点
那些争议最大的编程观点
5款最佳正则表达式编辑调试器
5款最佳正则表达式编辑调试器
10个调试和排错的小建议
10个调试和排错的小建议
程序员最害怕的5件事 你中招了吗?
程序员最害怕的5件事 你中招了吗?
程序员眼里IE浏览器是什么样的
程序员眼里IE浏览器是什么样的
亲爱的项目经理,我恨你
亲爱的项目经理,我恨你
Web开发人员为什么越来越懒了?
Web开发人员为什么越来越懒了?
 程序员的样子
程序员的样子
什么才是优秀的用户界面设计
什么才是优秀的用户界面设计
写给自己也写给你 自己到底该何去何从
写给自己也写给你 自己到底该何去何从
程序员的一天:一寸光阴一寸金
程序员的一天:一寸光阴一寸金
程序员应该关注的一些事儿
程序员应该关注的一些事儿
当下全球最炙手可热的八位少年创业者
当下全球最炙手可热的八位少年创业者
代码女神横空出世
代码女神横空出世
程序员和编码员之间的区别
程序员和编码员之间的区别
初级 vs 高级开发者 哪个性价比更高?
初级 vs 高级开发者 哪个性价比更高?
为什么程序员都是夜猫子
为什么程序员都是夜猫子
做程序猿的老婆应该注意的一些事情
做程序猿的老婆应该注意的一些事情
中美印日四国程序员比较
中美印日四国程序员比较
程序员的鄙视链
程序员的鄙视链
老程序员的下场
老程序员的下场
我是如何打败拖延症的
我是如何打败拖延症的
老美怎么看待阿里赴美上市
老美怎么看待阿里赴美上市
编程语言是女人
编程语言是女人
程序员周末都喜欢做什么?
程序员周末都喜欢做什么?
60个开发者不容错过的免费资源库
60个开发者不容错过的免费资源库
总结2014中国互联网十大段子
总结2014中国互联网十大段子
聊聊HTTPS和SSL/TLS协议
聊聊HTTPS和SSL/TLS协议
科技史上最臭名昭著的13大罪犯
科技史上最臭名昭著的13大罪犯
看13位CEO、创始人和高管如何提高工作效率
看13位CEO、创始人和高管如何提高工作效率
我的丈夫是个程序员
我的丈夫是个程序员
十大编程算法助程序员走上高手之路
十大编程算法助程序员走上高手之路
Web开发者需具备的8个好习惯
Web开发者需具备的8个好习惯
程序员都该阅读的书
程序员都该阅读的书
“肮脏的”IT工作排行榜
“肮脏的”IT工作排行榜
一个程序员的时间管理
一个程序员的时间管理
程序员必看的十大电影
程序员必看的十大电影
我跳槽是因为他们的显示器更大
我跳槽是因为他们的显示器更大
软件开发程序错误异常ExceptionCopyright © 2009-2015 MyException 版权所有