数据结构概述

数据结构概述 数据结构

演示网页：Data Structure Visualization

二叉树：[单路 - 不在乎高度差 ]

xn’sum：直接往里插，不用在乎两侧的高度。傻傻的往里插就行嘞。【傻插】

1、每个节点最多有两颗子树(树分支)

2、左子树和右子树是有顺序的，同层级相邻节点，右边的值比左边大。

3、即使某节点只有一颗子树，也要区分左右子树。

在所有的树结构中，基本上都遵循左小右大的原则，最上层节点称之为跟节点，最下面的节点称之为叶子节点，也叫叶节点，中间的节点称之为枝节点。

平衡二叉树 [AVL树]：[单路 - 高度差 < 1 ]

平衡二叉树又称之为AVL树，之所以多了一个“平衡”二字，【是因为和二叉树相比较，左右树高度相差不高于1.】

红黑树 [R-B Tree]：

source ：红黑树(一)之 原理和算法详细介绍 - 如果天空不死 - 博客园

红黑树主要是用来存储有序的数据，时间复杂度是O(lgn)，效率非常高。左/右旋： 对x进行左旋，就是把x变成左节点。对y进行右旋，就是把y变成右节点。左旋右旋影响的都是他下面的那些元素。【左旋 - 参考点是当前左旋点的右下元素；右旋 - 相对参考点是当前右旋元素的左下元素 】。示意图如下：

LEFT-ROTATE(T, x)  
01  y ← right[x]            // 前提：这里假设x的右孩子为y。下面开始正式 *** 作
02  right[x] ← left[y]      // 将 “y的左孩子” 设为 “x的右孩子”，即 将β设为x的右孩子【y的左变成x的右，y的右 和 x的左不变】
03  p[left[y]] ← x          // 将 “x” 设为 “y的左孩子的父亲”，即 将β的父亲设为x
04  p[y] ← p[x]             // 将 “x的父亲” 设为 “y的父亲”
05  if p[x] = nil[T]       
06  then root[T] ← y                 // 情况1：如果 “x的父亲” 是空节点，则将y设为根节点
07  else if x = left[p[x]]  
08            then left[p[x]] ← y    // 情况2：如果 x是它父节点的左孩子，则将y设为“x的父节点的左孩子”
09            else right[p[x]] ← y   // 情况3：(x是它父节点的右孩子) 将y设为“x的父节点的右孩子”
10  left[y] ← x             // 将 “x” 设为 “y的左孩子”
11  p[x] ← y                // 将 “x的父节点” 设为 “y” 

   左/右旋： 对x进行左旋，就是把x变成左节点。对y进行右旋，就是把y变成右节点。左旋右旋影响的都是他下面的那些元素。【左旋 - 参考点是当前左旋点的右下元素；右旋 - 相对参考点是当前右旋元素的左下元素 】。示意图如下：

 左旋示例图(以x为节点进行左旋)：

                               z
   x                          /                  
  /       --(左旋)-->       x
 y   z                      /
                           y

对x进行左旋，意味着，将“x的右孩子”设为“x的父亲节点”；即，将 x变成了一个左节点(x成了为z的左孩子)！。 因此，左旋中的“左”，意味着“被旋转的节点将变成一个左节点”。

右旋示例图(以x为节点进行右旋)：

                               y
   x                                             
  /       --(右旋)-->           x
 y   z                            
                                   z

对x进行右旋，意味着，将“x的左孩子”设为“x的父亲节点”；即，将 x变成了一个右节点(x成了为y的右孩子)！ 因此，右旋中的“右”，意味着“被旋转的节点将变成一个右节点”。

B树：[多路 - 不会有高度差de，叶子节点、内部节点、根节点不会重复 ]

        B树与平衡二叉树相似，不同的是B树属于多叉树，又名 【平衡多路查找树】，数据库索引技术里大量使用是B树和B+树的数据结构，顾名思义，就是每个节点上可以存储多个数值元素。与平衡二叉树不同的是，B树所有的叶子节点都处于同一层级。不存在层级高度差的问题。

B 树的特征：

 每个节点最多有（m - 1）个关键字[可以存有键值对]；每个根节点最少可以有1个关键字；每个非根节点至少有（m / 2）个关键字；每个节点中的关键字都按从小到大的顺序排列，每个关键字的左子树中的所有关键字都 < ta，每个右子树关键字都 > ta 。so， 根节点关键字范围：1 < k < m -1;  非根节点关键字范围：（m / 2）< k < （m-1）

B+树 : [多路 - 对比B树：叶子节点是全key且链式存储 ]

B+树的特征：B+树其实和B树是非常相似的，我们首先看看相同点。

根节点至少一个元素非根节点元素范围：m/2 <= k <= m-1

不同点。

B+树有两种类型的节点：内部结点（也称索引结点）和叶子结点。内部节点就是非叶子节点，内部节点不存储数据，只存储索引，数据都存储在叶子节点。内部结点中的key都按照从小到大的顺序排列，对于内部结点中的一个key，左树中的所有key都小于它，右子树中的key都大于等于它。叶子结点中的记录也按照key的大小排列。每个叶子结点都存有相邻叶子结点的指针，叶子结点本身依关键字的大小自小而大顺序链接。父节点存有右孩子的第一个元素的索引。（xn的理解：只有像【0011和0012】这样嵌套形式的情况下才谈此问题的。）

增添规则 ： 裂开了就要往上进位。

为什么说B+树比B树更适合数据库索引？

source ：B树、B+树详解 - Assassinの - 博客园

1）B+树的磁盘读写代价更低

　　B+树的内部结点并没有指向关键字具体信息的指针。因此其内部结点相对B 树更小。如果把所有同一内部结点的关键字存放在同一盘块中，那么盘块所能容纳的关键字数量也越多。一次性读入内存中的需要查找的关键字也就越多。相对来说IO读写次数也就降低了；

2）B+树查询效率更加稳定

　　由于非终结点并不是最终指向文件内容的结点，而只是叶子结点中关键字的索引。所以任何关键字的查找必须走一条从根结点到叶子结点的路。所有关键字查询的路径长度相同，导致每一个数据的查询效率相当；

3）B+树便于范围查询（最重要的原因，范围查找是数据库的常态）

　　B树在提高了IO性能的同时并没有解决元素遍历的我效率低下的问题，正是为了解决这个问题，B+树应用而生。B+树只需要去遍历叶子节点就可以实现整棵树的遍历。而且在数据库中基于范围的查询是非常频繁的，而B树不支持这样的 *** 作或者说效率太低；不懂可以看看这篇解读-》范围查找