2-3-4树学习 | StriveZs的博客

2-3-4树学习

首先先对二叉树进行介绍: 二叉树表面上理解是:只有两个分叉 如图: 需要注意的是每一个的结点的左子节点都比该节点的值小,同理该节点的右节点都比该节点的值大。还有就是每一个节点都只能有一个key值。相对的来讲二叉树的的结点越多,高度也越高,那么查找效率也就越低。   2-3-4数:  需要注意的无论什么操作都要保证所有的结点高度一样! 特点是高度平衡 有名字就可以看出来的它的结点可以有2个3个4个。 具体的定义:

  1. 一个key有两个儿子结点。

如图: 2.两个key有三个儿子结点 如图: 3.三个key有四个儿子结点 如图: 一个例子: 分析上面的例子: 对于一个key值两个孩子结点的情况就和普通的二叉树一样。 对于两个key值三个孩子结点情况: 那中间的MO双key为例:L的值比M的值小所以为左孩子,N的值大于M但是小于O的值所以作为中间孩子,最后是Q它的值大于O的值所以作为右孩子。(需要注意的一点是:key M的值小于O的值) 对于三个key值的四个孩子结点情况: 只能以上上面的图为例: abc三个key是由小到大排列的,p的值小于a,q的值大于a但是小于b,r的值大于b但是小于c的值,s的值大于c的值。 2-3-4数的查找其实和不同的二叉树查找相差不多,主要是都是通过递归实现。 主要流程:

  1. 首先和根节点比较如果小则以左孩子作为作为下一次的根节点
  2. 如果大则以右孩子作为下一次的根节点

(但是有一点不同的是这里可能有两个key或者三个key值所以需要进行分区,以便于能够选择到每个孩子)

  1. 如果最终能找到相同的值,则返回并提示查找成功,否则当遍历完该树时,结束并且返回查找失败。

图解: 2-3-4插入   插入分别几种情况: 1. 如果是向2 key值的结点插入数据的话,那么直接将它转换为3 key值的结点就好了。 如图: 3.如果是向一个3 key值的结点插入,则就将3 key值的结点变换为4 key值的结点 如图: 、 4.向四结点的插入节点的情况: 就需要对节点进行变化。 第一种情况: 向3 key值的结点插入,其父结点不是3 key值的结点,则进行如图操作: 则将FGJ中的G提到父结点中(注意这里的父结点不是3 key值的结点) 3 key结点的父结点分别为1 key结点和2 key结点不是3 key结点: 会在明天的 博文中讨论向一个三key值的结点插入数据时父结点也是3key值结点时的情况。 在这里要感谢:https://www.jianshu.com/p/37c845a5add6   博主提供的讲解,上面的图均取自其的博文,再次感谢。

StriveZs wechat
Hobby lead  creation, technology change world.
  • Post author: StriveZs
  • Post link: 1218.html
  • Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 3.0 unless stating additionally.