`

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

阅读更多

      从第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

分享到:
评论

相关推荐

    数据结构,算法与应用 ---C++语言描述(代码与习题答案)

    3. **C++实现**:C++支持面向对象编程,通过类和对象可以更好地封装数据和行为,实现数据结构和算法。模板机制允许创建泛型代码,增强了代码的复用性。此外,C++标准库提供了丰富的容器(如vector、list、set、map)...

    数据结构与算法经典问题解析-Java语言描述

    数据结构与算法是计算机科学的基础,对于任何编程语言来说,理解和掌握它们都是至关重要的,特别是对于Java开发者。这本书“数据结构与算法经典问题解析-Java语言描述”旨在帮助读者深入理解这些概念,并通过具体的...

    数据结构算法与应用--C++语言描述(代码与习题答案)

    在《数据结构算法与应用--C++语言描述》这本书中,作者深入浅出地介绍了各种基本和高级的数据结构及其对应的算法,并提供了详细的C++实现。以下是基于这个主题的详细知识点讲解: 1. **数组**:数组是最基础的数据...

    数据结构和算法-思维导图.pdf

    - 数据结构的遍历形态,如B树、B+树、2-3树、2-3-4树。 - 平衡二叉树、红黑树、AVL树、满二叉树、完全二叉树。 8. **图论基础**: - 图的遍历形态,如广度优先搜索、深度优先搜索、中序遍历、前序遍历、后序遍历...

    数据结构与算法分析-------

    - **章节10:2-3-4树与外部存储**(第335页):介绍2-3-4树这一自平衡树结构,以及如何在有限内存条件下高效管理大量数据。 - **章节11:哈希表**(第372页):探讨哈希表的工作原理及其优化策略。 - **章节12:...

    hello-algo-数据结构与算法-zh-csharp.pdf

    2. 数组、链表、栈、队列、树、图等数据结构的定义和应用 3. 算法的定义和分类 4. 排序、查找、图形遍历等算法的定义和应用 5. 数据结构与算法在编程中的应用 6. 如何学习数据结构与算法 7. 数据结构与算法的知识...

    数据结构与算法(Java版-英文)

    - **第10章:2-3-4树与外部存储** - 阐述2-3-4树这一多路搜索树的特点,并介绍其在数据库索引和外部存储管理中的应用。 - **第11章:哈希表** - 分析哈希表的工作原理,包括哈希函数的设计、冲突解决策略以及在高速...

    2021.6-数据结构与算法设计项目---校园导航.7z

    总之,这个校园导航项目涵盖了数据结构、算法和C语言的基础知识,同时也涉及到软件工程中的文件处理、错误处理和性能优化等方面。通过参与这样的项目,开发者不仅可以提升编程技能,还能深入理解如何将理论知识应用...

    2018JAVA经典教程:数据结构与算法经典问题解析-Java语言描述

    《2018JAVA经典教程:数据结构与算法经典问题解析》是一本深入探讨Java语言中数据结构和算法实现的教程。这本书旨在帮助读者理解并掌握如何使用Java有效地设计和解决各种计算问题。数据结构是计算机科学的基础,而算...

    数据结构,算法与应用 ---C++语言描述代码 (包括习题)

    4. **代码实践**:书中包含的代码示例有助于读者掌握如何在C++中实现各种数据结构和算法。这些代码可能包括数据结构的定义、操作函数以及算法的具体实现。通过阅读和分析这些代码,学习者可以提升编程技巧和问题解决...

    数据结构和算法Flash动画演示-整理后

    数据结构和算法是计算机科学的基础,对于理解和设计高效的软件至关重要。本资源“数据结构和算法Flash动画演示-整理后”提供了生动形象的方式,帮助学习者深入理解这些抽象概念。通过Flash动画的形式,使得复杂的...

    数据结构与算法----面向对象的C++模式

    全书分16章,1概论,2算法分析 3渐进表示法 4基本数据结构,5数据类型与抽象 6栈与队列 7有序线性表与排序表 8 散列,哈希表与分散表 9树 10查找树, 11堆和优先队列 12集合,多重集和分区 13动态存储分配 14 算法...

    数据结构与算法-java

    数据结构与算法是计算机科学的基础,对于理解和设计高效的软件至关重要。在Java编程中,理解这些概念可以帮助开发者编写出性能优异的程序。以下是基于标题“数据结构与算法-java”及描述中提到的“数据结构与算法...

    java数据结构与算法.pdf

    - **普里姆算法**:最小生成树算法,用于找到图中边权重之和最小的树结构。 - **迪杰斯特拉算法**:单源最短路径算法,适用于加权无环图。 - **弗洛伊德算法**:多源最短路径算法,可以找出图中所有点对之间的...

    2-3树的实现

    2-3树在中南大学计算机系研究生的高级算法课程中是一个重要的内容,适合于学习数据结构和算法的学生。 2-3树的结构特点: 1. 每个节点可以包含两个或三个子节点,故名2-3树。 2. 所有的叶子节点都在同一层。 3. 2-...

    算法与数据结构--空间复杂度O-1-遍历树.rar

    《算法与数据结构--空间复杂度O-1-遍历树》这个压缩包文件主要探讨的是在算法设计和数据结构领域中的一个特定话题:如何在有限的空间复杂度下,高效地遍历树型数据结构。这涉及到计算机科学的基础知识,特别是在优化...

    算法数据结构体系学习班课程-视频教程网盘链接提取码下载 .txt

    ### 算法数据结构体系学习班课程概览 #### 一、课程定位与目标 本课程《算法数据结构体系学习班》专为初学者设计,旨在帮助学员系统地掌握算法与数据结构的基础知识,同时培养学员运用所学解决实际问题的能力。...

    湖南大学-数据结构-期末试题【2016-2019】.zip

    数据结构是计算机科学中的核心课程,它探讨了如何在计算机中高效地组织和管理数据,以便于进行各种操作。湖南大学的数据结构期末试题涵盖了这门课程的重要概念和技术,旨在检验学生对这些知识的理解和应用能力。以下...

Global site tag (gtag.js) - Google Analytics