文档章节

数据结构和算法06 之2-3-4树

乐在克里特
 乐在克里特
发布于 2017/02/23 13:53
字数 2190
阅读 4
收藏 0

      从第4节的分析中可以看出,二叉搜索树是个很好的数据结构,可以快速地找到一个给定关键字的数据项,并且可以快速地插入和删除数据项。但是二叉搜索树有个很麻烦的问题,如果树中插入的是随机数据,则执行效果很好,但如果插入的是有序或者逆序的数据,那么二叉搜索树的执行速度就变得很慢。因为当插入数值有序时,二叉树就是非平衡的了,它的快速查找、插入和删除指定数据项的能力就丧失了。

    2-3-4树是一个多叉树,它的每个节点最多有四个子节点和三个数据项。2-3-4树和红-黑树一样,也是平衡树,它的效率比红-黑树稍差,但是编程容易。2-3-4树名字中的2、3、4的含义是指一个节点可能含有的子节点的个数。对非叶节点有三种可能的情况:

    ·有一个数据项的节点总是有两个子节点;

    ·有两个数据项的节点总是有三个子节点;

    ·有三个数据项的节点总是有四个字节点。

    简而言之,非叶节点的子节点总是比它含有的数据项多1。如下图所示:

 

    为了方便起见,用0到2给数据项编号,用0到3给子节点链编号。树的结构中很重要的一点就是它的链与自己数据项的关键字值之间的关系。二叉树所有关键字值比某个节点值小的都在这个节点的左子节点为根的子树上,所有关键字值比某个及诶的那值大的节点都在这个节点右子节点为根的子树上。2-3-4树中规则是一样的,还加上了以下几点:

    ·根是child0的子树的所有子节点的关键字值小于key0;

    ·根是child1的子树的所有子节点的关键字值大于key0并且小于key1;

    ·根是child2的子树的所有子节点的关键字值大于key1并且小于key2;

    ·根是child3的子树的所有子节点的关键字值大于key2。

    这种关系如下图所示,2-3-4树中一般不允许出现重复关键字值,所以不用考虑比较相同的关键字值的情况。

    2-3-4树中插入节点有时比较简单,有时比较复杂。当没有碰到满节点时插入很简单,找到合适的叶节点后,只要把新数据项插入进去即可,插入可能会涉及到在一个节点中移动一个或两个其他的数据项,这样在新的数据项插入后关键字值仍保持正确的顺序。如下图:

 

    如果往下寻找要插入的位置的路途中,节点已经满了,插入就变得复杂了。这种情况下,节点必须分裂。正是这种分裂过程保证了树的平衡。设要分裂节点中的数据项为A、B、C,下面是分裂时的情况(假设分裂的节点不是根节点):

    ·创建一个新的空节点,它是要分裂节点的兄弟,在要分裂节点的右边;

    ·数据项C移到新节点中;

    ·数据项B移动到要分裂节点的父节点中;

    ·数据项A保留在原来的位置;

    ·最右边的两个子节点从要分裂节点处断开,连接到新节点上。

    下图显示了一个节点分裂的过程。另一种描述节点分裂的方法是说4-节点变成了两个2-节点。

 

    如果一开始查找插入点时就碰到满根时,插入过程就更复杂一点:

    ·创建新的根。它是要分裂节点的父节点;

    ·创建第二个新的节点。它是要分裂节点的兄弟节点;

    ·数据项C移动到新的兄弟节点中;

    ·数据项B移动到新的根节点中;

    ·数据项A保留在原来的位置上;

    ·要分裂节点最右边的两个子节点断开连接,连接到新的兄弟节点中。

    下图是根分裂的过程。过程中创建新的根,比旧的高一层,因此整个树的高度就增加了一层。

 

    下面是2-3-4树的代码:

 

  1. public class Tree234 {  
  2.     private Node2 root = new Node2();  
  3.     public int find(long key) {  
  4.         Node2 currentNode = root;  
  5.         int childNumber;  
  6.         while(true) {  
  7.             if((childNumber = currentNode.findItem(key)) != -1) {  
  8.                 return childNumber;  
  9.             }  
  10.             else if(currentNode.isLeaf()) {  
  11.                 return -1;  
  12.             }  
  13.             else {  
  14.                 currentNode = getNextChild(currentNode, key);  
  15.             }  
  16.         }  
  17.     }  
  18.     //insert a DataItem  
  19.     public void insert(long data) {  
  20.         Node2 currentNode = root;  
  21.         DataItem tempItem = new DataItem(data);  
  22.         while(true) {  
  23.             if(currentNode.isFull()) {  
  24.                 split(currentNode); //if node is full, split it  
  25.                 currentNode = currentNode.getParent();  //back up  
  26.                 currentNode = getNextChild(currentNode, data);  //search once  
  27.             }  
  28.             else if(currentNode.isLeaf()) { //if node if leaf  
  29.                 break;  //go insert  
  30.             }  
  31.             else {  
  32.                 currentNode = getNextChild(currentNode, data);  
  33.             }  
  34.         }  
  35.         currentNode.insertItem(tempItem);  
  36.     }  
  37.     //display tree  
  38.     public void displayTree() {  
  39.         recDisplayTree(root, 00);  
  40.     }  
  41.     public Node2 getNextChild(Node2 currentNode, long key) {  
  42.         int j;  
  43.         //assumes node is not empty, not full and not leaf  
  44.         int numItems = currentNode.getNumItems();  
  45.         for(j = 0; j < numItems; j++) {  
  46.             if(key < currentNode.getItem(j).dData) {  
  47.                 return currentNode.getChild(j);  
  48.             }  
  49.         }  
  50.         return currentNode.getChild(j);  
  51.     }  
  52.     public void split(Node2 currentNode) {  
  53.         //assumes node is full  
  54.         DataItem itemB, itemC;  //存储要分裂节点的后两个DataItem  
  55.         Node2 parent, child2, child3;   //存储要分裂节点的父节点和后两个child  
  56.         int itemIndex;  
  57.         itemC = currentNode.removeItem();  
  58.         itemB = currentNode.removeItem();   //remove items from this node  
  59.         child2 = currentNode.disconnectChild(2);  
  60.         child3 = currentNode.disconnectChild(3); //remove children from this node  
  61.         Node2 newRight = new Node2(); //make a new node  
  62.         if(currentNode == root) {  
  63.             root = new Node2(); //make a new root  
  64.             parent = root;  //root is our parent  
  65.             root.connectChild(0, currentNode);//connect currentNode to parent  
  66.         }  
  67.         else {  
  68.             parent = currentNode.getParent();  
  69.         }  
  70.         //deal with parent  
  71.         itemIndex = parent.insertItem(itemB);   //insert B to parent  
  72.         int n = parent.getNumItems();   //total items  
  73.         for(int j = n-1; j > itemIndex; j--) {  
  74.             Node2 temp = parent.disconnectChild(j);  
  75.             parent.connectChild(j+1, temp);  
  76.         }  
  77.         parent.connectChild(itemIndex+1, newRight);  
  78.         //deal with newRight  
  79.         newRight.insertItem(itemC);  
  80.         newRight.connectChild(0, child2);  
  81.         newRight.connectChild(1, child3);  
  82.     }  
  83.     public void recDisplayTree(Node2 thisNode, int level, int childNumber) {  
  84.         System.out.print("level = " + level + " child = " + childNumber + " ");  
  85.         thisNode.displayNode();  
  86.         //call ourselves for each child of this node  
  87.         int numItems = thisNode.getNumItems();  
  88.         for(int j = 0; j < numItems+1; j++) {  
  89.             Node2 nextNode = thisNode.getChild(j);  
  90.             if(nextNode != null) {  
  91.                 recDisplayTree(nextNode, level+1, j);  
  92.             }  
  93.             else   
  94.                 continue;  
  95.         }  
  96.     }  
  97. }  
  98.   
  99. //数据项  
  100. class DataItem {  
  101.     public long dData;  
  102.     public DataItem(long data) {  
  103.         dData = data;  
  104.     }  
  105.     public void displayItem() {  
  106.         System.out.print("/" + dData);  
  107.     }  
  108. }  
  109. //节点  
  110. class Node2 {  
  111.     private static final int ORDER = 4;  
  112.     private int numItems; //表示该节点存有多少个数据项  
  113.     private Node2 parent;  
  114.     private Node2 childArray[] = new Node2[ORDER]; //存储子节点的数组,最多四个子节点  
  115.     private DataItem itemArray[] = new DataItem[ORDER-1];//该节点中存放数据项的数组,每个节点最多存放三个数据项  
  116.     //连接子节点  
  117.     public void connectChild(int childNum, Node2 child) {  
  118.         childArray[childNum] = child;  
  119.         if(child != null) {  
  120.             child.parent = this;  
  121.         }  
  122.     }  
  123.     //断开与子节点的连接,并返回该子节点  
  124.     public Node2 disconnectChild(int childNum) {  
  125.         Node2 tempNode = childArray[childNum];  
  126.         childArray[childNum] = null;  
  127.         return tempNode;  
  128.     }  
  129.     public Node2 getChild(int childNum) {  
  130.         return childArray[childNum];  
  131.     }  
  132.     public Node2 getParent() {  
  133.         return parent;  
  134.     }  
  135.   
  136.     public boolean isLeaf() {  
  137.         return (childArray[0] == null);  
  138.     }  
  139.     public int getNumItems() {  
  140.         return numItems;  
  141.     }  
  142.     public DataItem getItem(int index) {  
  143.         return itemArray[index];  
  144.     }  
  145.     public boolean isFull() {  
  146.         return (numItems == ORDER-1);  
  147.     }  
  148.     public int findItem(long key) {  
  149.         for(int j = 0; j < ORDER-1; j++) {  
  150.             if(itemArray[j] == null) {  
  151.                 break;  
  152.             }  
  153.             else if(itemArray[j].dData == key) {  
  154.                 return j;  
  155.             }  
  156.         }  
  157.         return -1;  
  158.     }  
  159.     public int insertItem(DataItem newItem) {  
  160.         //assumes node is not full  
  161.         numItems++;  
  162.         long newKey = newItem.dData;  
  163.         for(int j = ORDER-2; j >= 0; j--) {  //start on right  
  164.             if(itemArray[j] == null) {      //item is null  
  165.                 continue;                   //get left one cell  
  166.             }  
  167.             else {                          //not null  
  168.                 long itsKey = itemArray[j].dData;   //get its key  
  169.                 if(newKey < itsKey) {                //if it's bigger  
  170.                     itemArray[j+1] = itemArray[j];  //shift it right  
  171.                 }  
  172.                 else {  
  173.                     itemArray[j+1] = newItem;       //insert new item  
  174.                     return j+1;                     //return index to new item  
  175.                 }  
  176.             }  
  177.         }  
  178.         itemArray[0] = newItem;  
  179.         return 0;  
  180.     }  
  181.     public DataItem removeItem() {  
  182.         //assumes node not empty  
  183.         DataItem tempItem = itemArray[numItems-1];  //save item  
  184.         itemArray[numItems-1] = null;               //disconnect it  
  185.         numItems--;  
  186.         return tempItem;  
  187.     }  
  188.     public void displayNode() {  
  189.         for(int i = 0; i < numItems; i++) {  
  190.             itemArray[i].displayItem();  
  191.         }  
  192.         System.out.println("/");  
  193.     }  
  194. }  

    和红-黑树一样,2-3-4树同样要访问每层的一个节点,但2-3-4树有比相同数据项的红-黑树短(层数少)。更特别的是,2-3-4树中每个节点最多可以有4个子节点,如果每个节点都是满的,树的高度应该和log4N成正比。以2为底的对数和以4为底的对数底数相差2,因此,在所有节点都满的情况下,2-3-4树的高度大致是红-黑树的一般。不过它们不可能都是满的,2-3-4树的高度就大致在log2(N+1)和log2(N+1)/2之间。

    另一方面,每个节点要查看的数据项就更多了,这会增加查找时间。因为节点中用线性搜索来查看数据项,使查找时间增加的倍数和M成正比,即每个节点数据项的平均数量。总的查找时间和M*log4N成正比。有些节点有1个数据项,有些有2个,有些有3个,如果按照平均两个来计算,查找时间和2*log4N成正比。

      因此,2-3-4树中增加每个节点的数据项数量可以抵偿树的高度的减少。2-3-4树中的查找时间与平衡二叉树(如红-黑树)大致相等,都是O(logN)。

 

http://blog.csdn.net/eson_15/article/details/51140009

© 著作权归作者所有

共有 人打赏支持
乐在克里特
粉丝 15
博文 268
码字总数 394729
作品 0
杭州
程序员
私信 提问
数据结构课程主页-2016级

  新学期,再度起程!   翻转的数据结构课程再度迎来新的一批同学。   前两年,资源建设基本完备,课堂方案逐渐完善,同学们对新型的学习方式设计给予了肯定(参见2014级问卷调查和201...

sxhelijian
2017/08/30
0
0
用js来实现那些数据结构及算法—目录

  首先,有一点要声明,下面所有文章的所有内容的代码,都不是我一个人独立完成的,它们来自于一本叫做《学习JavaScript数据结构和算法》(第二版),人民邮电出版社出版的这本书。github代...

zaking
05/10
0
0
【备忘】2017年最新黑马Python全套内含解压密码

2017年最新黑马Python全套视频教程 ├─01基础 │ │ 第1节 linux操作系统基础.zip │ │ 第2节 python语法基础.zip │ │ 第3节 项目-飞机大战.zip │ │ 补充资料.zip │ │ │ └─第1节 ...

qq_38155396
2017/06/30
0
0
算法和编程面试题精选 TOP50!(附代码+解题思路+答案)

作者 | javinpaul 出品 | AI科技大本营 数组 数组,将元素存储到内存的连续位置中,是最基本的数据结构。在任何和编程相关的面试中,都会被问到和数组相关的问题,可以说是非常热门的考题之一...

CSDN资讯
10/02
0
0
算法和编程面试题精选TOP50!(附代码+解题思路+答案)

作者 | javinpaul 编译 | 王天宇、Jane 整理 | Jane 出品 | AI科技大本营 【导读】之前我们给同学们推荐了很多关于 Python 的面试资源,大家都表示很有用。这次营长表示要翻 Java 的牌子啦~...

AI科技大本营
09/27
0
0

没有更多内容

加载失败,请刷新页面

加载更多

ViewPager+Fragment+FragmentPagerAdapter实现软件主界面

ViewPager之前的页面是由View构成的,现在由Fragment构成,之前的PagerAdapter这里也换成了FragmentPagerAdapter.因为PagerAdapter有 public Object instantiateItem(ViewGroup container, i......

鱼想吃肉
17分钟前
0
0
feign文件上传遇到的坑

明天写

王俊博客
22分钟前
0
0
scala的sorted,sortBy,sortWith

val lst = List(1,3,2,4,5) //scala中对于集合的排序有三种方法:sorted,sortBy,sortWith //sorted方法对一个集合进行自然排序,传递一个Ordering隐式参数 def sorted[B >: A](imp...

whoisliang
37分钟前
0
0
区块链扩容最佳途径?十分钟讲清楚侧链技术

今天我们来讲区块链扩容的另一个主流方案——侧链,侧链可作为解决区块链扩容难题的一种有效解决方案。有些人认为,从理论上说,这种解决方案可让所有人都满意。 基础概念 侧链协议本质上是一...

HiBlock
39分钟前
0
0
3年经验Java程序员面阿里P6 差距在哪里

虽然这位小伙伴觉得自己工作三年了,结果阿里连面都不面就把自己挂了,这让自己感到很伤心。但是还是有网友觉得,三年不到p6,很正常啊,明年再面就没有问题啦! Java程序员3年经验面阿里P6,...

架构师springboot
41分钟前
1
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部