• 极客专栏正式上线!欢迎访问 https://www.jikewenku.com/topic.html
  • 极客专栏正式上线!欢迎访问 https://www.jikewenku.com/topic.html

2-3-4树是如何解决二叉树中非平衡问题的?

技术杂谈 勤劳的小蚂蚁 4个月前 (01-14) 88次浏览 已收录 0个评论 扫描二维码


我之前写过一篇文章:下次面试若再被问到二叉树,希望你能对答如流!没错,二叉搜索树是个很好的数据结构,可以快速地找到一个给定关键字的数据项,并且可以快速地插入和删除数据项。
但是二叉搜索树有个很麻烦的问题,如果树中插入的是随机数据,则执行效果很好,但如果插入的是有序或者逆序的数据,那么二叉搜索树的执行速度就变得很慢。因为当插入数值有序时,二叉树就是非平衡的了,它的快速查找、插入和删除指定数据项的能力就丧失了。
为了解决这个问题,我们可以使用多叉树。
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. publicclassTree234 {
  2.    privateNode2 root = newNode2();
  3.    publicint 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.            elseif(currentNode.isLeaf()) {
  11.                return -1;
  12.            }
  13.            else {
  14.                currentNode = getNextChild(currentNode, key);
  15.            }
  16.        }
  17.    }
  18.    //insert a DataItem
  19.    publicvoid insert(long data) {
  20.        Node2 currentNode = root;
  21.        DataItem tempItem = newDataItem(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.            elseif(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.    publicvoid displayTree() {
  39.        recDisplayTree(root, 0, 0);
  40.    }
  41.    publicNode2 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.    publicvoid 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 = newNode2(); //make a new node
  62.        if(currentNode == root) {
  63.            root = newNode2(); //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.    publicvoid 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. classDataItem {
  100.    publiclong dData;
  101.    publicDataItem(long data) {
  102.        dData = data;
  103.    }
  104.    publicvoid displayItem() {
  105.        System.out.print("/" + dData);
  106.    }
  107. }
  108. //节点
  109. classNode2 {
  110.    privatestaticfinalint ORDER = 4;
  111.    privateint numItems; //表示该节点存有多少个数据项
  112.    privateNode2 parent;
  113.    privateNode2 childArray[] = newNode2[ORDER]; //存储子节点的数组,最多四个子节点
  114.    privateDataItem itemArray[] = newDataItem[ORDER-1];//该节点中存放数据项的数组,每个节点最多存放三个数据项
  115.    //连接子节点
  116.    publicvoid connectChild(int childNum, Node2 child) {
  117.        childArray[childNum] = child;
  118.        if(child != null) {
  119.            child.parent = this;
  120.        }
  121.    }
  122.    //断开与子节点的连接,并返回该子节点
  123.    publicNode2 disconnectChild(int childNum) {
  124.        Node2 tempNode = childArray[childNum];
  125.        childArray[childNum] = null;
  126.        return tempNode;
  127.    }
  128.    publicNode2 getChild(int childNum) {
  129.        return childArray[childNum];
  130.    }
  131.    publicNode2 getParent() {
  132.        return parent;
  133.    }
  134.    publicboolean isLeaf() {
  135.        return (childArray[0] == null);
  136.    }
  137.    publicint getNumItems() {
  138.        return numItems;
  139.    }
  140.    publicDataItem getItem(int index) {
  141.        return itemArray[index];
  142.    }
  143.    publicboolean isFull() {
  144.        return (numItems == ORDER-1);
  145.    }
  146.    publicint findItem(long key) {
  147.        for(int j = 0; j < ORDER-1; j++) {
  148.            if(itemArray[j] == null) {
  149.                break;
  150.            }
  151.            elseif(itemArray[j].dData == key) {
  152.                return j;
  153.            }
  154.        }
  155.        return -1;
  156.    }
  157.    publicint insertItem(DataItem newItem) {
  158.        //assumes node is not full
  159.        numItems++;
  160.        long newKey = newItem.dData;
  161.        for(int j = ORDER-2; j >= 0; j--) {     //start on right
  162.            if(itemArray[j] == null) {      //item is null
  163.                continue;                   //get left one cell
  164.            }
  165.            else {                          //not null
  166.                long itsKey = itemArray[j].dData;   //get its key
  167.                if(newKey < itsKey) {               //if it's bigger
  168.                    itemArray[j+1] = itemArray[j];  //shift it right
  169.                }
  170.                else {
  171.                    itemArray[j+1] = newItem;       //insert new item
  172.                    return j+1;                     //return index to new item
  173.                }
  174.            }
  175.        }
  176.        itemArray[0] = newItem;
  177.        return0;
  178.    }
  179.    publicDataItem removeItem() {
  180.        //assumes node not empty
  181.        DataItem tempItem = itemArray[numItems-1];  //save item
  182.        itemArray[numItems-1] = null;               //disconnect it
  183.        numItems--;
  184.        return tempItem;
  185.    }
  186.    publicvoid displayNode() {
  187.        for(int i = 0; i < numItems; i++) {
  188.            itemArray[i].displayItem();
  189.        }
  190.        System.out.println("/");
  191.    }
  192. }

和红-黑树一样,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成正比,即每个节点数据项的平均数量。总的查找时间和Mlog4N成正比。有些节点有1个数据项,有些有2个,有些有3个,如果按照平均两个来计算,查找时间和2log4N成正比。
因此,2-3-4树中增加每个节点的数据项数量可以抵偿树的高度的减少。2-3-4树中的查找时间与平衡二叉树(如红-黑树)大致相等,都是O(logN)。
本文建议收藏,在等班车的时候、吃饭排队的时候可以拿出来看看。利用碎片化时间来学习!

丨极客文库, 版权所有丨如未注明 , 均为原创丨
本网站采用知识共享署名-非商业性使用-相同方式共享 3.0 中国大陆许可协议进行授权
转载请注明原文链接:2-3-4树是如何解决二叉树中非平衡问题的?
喜欢 (0)
[247507792@qq.com]
分享 (0)
勤劳的小蚂蚁
关于作者:
温馨提示:本文来源于网络,转载文章皆标明了出处,如果您发现侵权文章,请及时向站长反馈删除。

您必须 登录 才能发表评论!

  • 精品技术教程
  • 编程资源分享
  • 问答交流社区
  • 极客文库知识库

客服QQ


QQ:2248886839


工作时间:09:00-23:00