首页 > 其他 > 详细

算法5-1:平衡查找树之二三树

时间:2014-06-19 11:26:38      阅读:314      评论:0      收藏:0      [点我收藏+]

标签:算法   二叉树   二三树   

平衡查找树的目标是实现查找、插入、删除操作在最坏情况下的复杂度均为logN。


本节将介绍二三查找树。


二三树中有两种节点:

  • 二节点对应一个键,有两个子节点

  • 三节点对应两个键,有三个子节点


二三查找树非常平衡,每个空节点到根节点的距离都是一样的 。


查找操作


在二三树中查找一个键的时候有以下规则:

  • 如果是二节点,二节点对应1个值,如果要查找的值比该节点对应的值小,就往左侧深入,反之亦成

  • 如果是三节点,三节点对应2个值,如果比两个值都小,就往左侧深入,如果介于两个值之间,就往中间深入,如果比两个值都大,就往右侧深入。


插入操作


根据查找操作的规则,先定位到需要插入的节点。如果是二节点,那么将二节点中增加一个键成为三节点。如果是三节点,在三节点中增加1个键成为四节点。由于四节点不允许在二三树中出现,因此需要分解成两个二节点,并且把中间的键提取到父节点中。下图展示四节点分解的过程:


现在要在这棵树中插入一个值7

bubuko.com,布布扣


首先根据查找操作的规则定位到要插入的节点,定位之后是如图所示的节点

bubuko.com,布布扣


由于该节点是三节点,因此插入一个键,使它成为四节点

bubuko.com,布布扣


由于四节点不允许在2-3树中存在,因此需要将其分解为两个二节点,并把中间的键7提到父节点中

bubuko.com,布布扣


这样插入操作就完成了


性能


2-3树的高度介于lgN和log_3(N)之间,因此能够保证所有的操作复杂度均在logN以下


实现


二三树的实现非常复杂,因为要判断每个节点的类型,插入节点的时候还需要判断插入节点的位置,需要考虑的情况非常多。


算法5-1:平衡查找树之二三树,布布扣,bubuko.com

算法5-1:平衡查找树之二三树

标签:算法   二叉树   二三树   

原文:http://blog.csdn.net/caipeichao2/article/details/30089151

(0)
(0)
   
举报
评论 一句话评论(0
© 2014 bubuko.com 版权所有 鲁ICP备09046678号-4
打开技术之扣,分享程序人生!
             

鲁公网安备 37021202000002号