一、 二叉平衡树的时间复杂度

  在数据结构(五):树中的二叉查找树中,我们发现当二叉树平衡时,我们查找一个元素需要遍历的层级是log(N+1),按照大O算法可得时间复杂度为logN,这种查找比链表和数组的O(N)算法要

  高效得多。

   

       但是当二叉树不平衡时,我们发现它的查找效率依旧是O(N),比如如下情况:

        

二、 2-3树概述

  为了保证二叉树的平衡,提高树查找的效率,减少遍历的层级,我们允许一个结点保留多个键,并且链接的不止两条链

   

  2-结点:

  含有一个键和两条链,左链指向的键都小于该结点,右链指向的键都大于该结点

  3-结点:

  含有两个键和三条链,左链指向的键都小于该结点,右链指向的键都大于该结点,中链指向的的键介于该结点的两个键之间

  注:2-3树中不允许有大于等于3个键的结点存在

三、 2-3查找树

  2-3树的查找思路与二叉查找树相似,对于需要查找的键,从根结点开始遍历,小于往左,大于则往右,当找到3-结点时,若查找的键介于3-结点的两个键之间,则找中链接对应的结点,命中则返回。

  查找过程没命中时则继续递归查找子树。

  如图:查找键为H的结点,首先找根结点M,由于H<M,往下找左子树

   

  查找到左子树为3-结点,判断H>E并且H<J,则找中链结点的键

   

四、 2-3树的插入

  往2-3树中插入结点的思路和二叉树一致,首先进行查找,根据2-3树的特性将结点挂到合适的位置,保持树的平衡。由于2-3树既包含2-结点同时也包含3-结点,因此在插入时针对不同类型的结点

  有不同的处理方式:

  一、 往2-结点中插入新键

  插入K:往2-结点中插入新键时,我们可以保证树层级不变的基础上,将2-结点转化为3-结点

   

  二、 往只有一个3-结点中插入新键

   

  往3-根结点中插入S

   

  将中键提升为根结点,左右两键成为左右子树

   

  三、 往一个父结点为2-结点的3-结点中插入新键

  往该2-3树中插入元素Z

   

  

  将3-结点的中间元素往上提

   

  四、 往一个父结点为3-结点的3-结点中插入新键

  往该2-3树中插入元素D

   

   

  将插入后形成的3-结点往上提

   

  将形成的3-父节点再次取中间值往上提升一层

   

  五、 插入结点到根结点的路径上是3-结点

  往该2-3树中插入D

  

   

  将插入后形成的3-结点取中间值往上提

   

  将形成的3-根结点再次分解

   

五、 2-3树总结

  5.1平衡的2-3树特性:

  (1)任意空链接到根结点的长度是相等的

  (2)非根结点的4-(3个键)结点变化为3-结点时,树高不变,只有当4-结点为根结点,分解后树的高度才会+1

  (3)2-3树与普通二叉树相比,不同的是2-3树自底向上生长,普通二叉树自顶向下生长。

  5.2引入2-3树思想的理由

  2-3树本身的实现是很困难的,引入2-3树的思想是为了下一章节的红黑树做铺垫


发布评论
IT源码网

微信公众号号:IT虾米 (左侧二维码扫一扫)欢迎添加!

数据结构(五):树讲解
你是第一个吃螃蟹的人
发表评论

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。