网站开发 搜索,做网络投票网站好做吗,网页设计需要学什么编程,手机制作app工具普通树一个结点可以有多个孩子#xff0c;但它本身只能存储一个元素#xff0c;而二叉树结点最多只能有两个#xff0c;这对于元素非常多的时候#xff0c;会使得树的度或者是高度会非常大。这就使得内存存取外存的次数会增多#xff0c;一旦涉及到外部存储设备#xff0… 普通树一个结点可以有多个孩子但它本身只能存储一个元素而二叉树结点最多只能有两个这对于元素非常多的时候会使得树的度或者是高度会非常大。这就使得内存存取外存的次数会增多一旦涉及到外部存储设备时间复杂度的计算就会受到影响所以为了降低对外存设备的访问次数就引入了一个叫多路查找树(mutil-way search tree)的数据结构。 多路查找树其每一个结点的孩子数可以多于两个且每一个结点可以存储多个元素。多路查找树有查找的性质所以所有元素之间又存在着特定的排序关系。多路查找树的4种特殊形式2-3树、2-3-4树、B树和B树 最开始说说最简单的B树2-3树 1.1 概念 2-3树其中的每个非叶子结点都具有两个孩子(2结点)或三个孩子(3结点)。高度为h的2-3树结点数至少有2^h - 1个。 2结点包含一个元素S和两个孩子(或没有孩子)。元素S大于左子树包含的元素小于右子树包含的元素。 3结点包含两个元素S和L以及三个孩子(或没有孩子)。元素S大于左子树包含的元素且小于中间子树包含的元素元素L大于中间子树包含的元素小于右子树包含的元素。 且所有叶子结点都在同一层次。 1.2 操作2-3树 1.2.1 查找元素 2-3树的查找方式与二叉树类似根据元素与结点的大小比对决定后续路线。如上图我需要找个10首先2结点10 8往右子树找下一结点包含两个元素为3结点10 12往左子树找左子树中比较查找得到10。 1.2.2 插入 2-3树的插入操作与二叉树相同插入操作一定是发生在叶子节点上。 1)对于一个空树来说插入一个2结点即可 2)插入结点到一个2结点的叶子上由于其本身就一个元素所以只需要将其变成3结点即可。 如上图我希望插入一个元素3根据遍历3 83 4于是考虑插入到叶子结点1所在位置3 1于是3在1的右边儿。 3)往3结点插入一个新元素就需要将其拆分且将树中两元素或插入元素的三者中选择其一向上移动一层。 来看看第一种情况插入的元素是5被插入的结点是(6,7)是一个3结点当父节点是2节点这时候考虑将567其中一人升一级4 5 6 5 6 7将6提上一层让父节点变为3节点5插入变成中间子树剩下一个7为右子树 另一种情况插入的元素是1111 12显然11应该插入到3节点(9,10)中但(9,10)节点不能再插入元素了于是考虑将11插入到(12,14)节点中这时候8 11 12,所以将12向上提一层这时候原来的拥有8元素的2结点变为了3结点剩下的11,9,10需要考虑将他们变为中子树 1.2.3 删除 1)所删除的元素位于3结点的叶子结点上直接删除即可。因为3结点中肯定是包含两个元素的直接删除也不会影响到2-3树的结构变化。如图我想要把元素9删除那么我直接剔除元素9即可 2)删除的元素位于2结点上即删除的是只有一个元素的结点相当于对结点进行删除操作。这个时候如果直接把结点删除便会不符合2-3树的定义(无子结点或必须拥有N个子节点)。如我想要删除元素1结点4本来是拥有子结点1与子结点6,7的此时少了结点1便不符合2-3树的定义了。 于是对于删除的元素处于2结点的位置时候需要分四种情况考虑 第一种结点双亲也是2结点且拥有一个3结点的孩子正如上图那么这时候只需要左旋将6元素提上一层即可 第二种结点的双亲是2结点右孩子也是2结点。这个时候就不能像上一种情况那样直接左旋这样会造成新的树形没有右孩子因此需要对整棵树进行变形来让拥有7元素的这个结点变为3结点。比如我删除了一个元素4的结点。这个时候需要让8加入到元素7的结点中然后让右子树最小的一位元素9到顶层最后左旋即可。 情形三此节点的双亲是一个3结点。比如说我删除一个元素10这个时候只需要将3结点的小元素降下来然后与中子树的合为一个3结点即可。 情形四当前的2-3树为一个满二叉树这个时候删除任何一个叶子都需要让整棵树变形。我从下图中删除一个8元素的结点这个时候9肯定不能单独作为一个2结点存在了考虑到2-3树的性质6与7合为一个3结点放左子树14提上一层13当做一个中子树15作为一个右子树
