你真的懂树吗(二叉树、AVL平衡二叉树、伸展树、B-树和B+树原理和实现代码详解)

树(Tree)是一种相当灵活的数据结构(上一节已经详细讲解了基本的数据结构:线性表、栈和队列),你可能接触过二叉树,但是树的使用并不限于此,从简单的使用二叉树进行数据排序,到使用B-树或B+树设计数据库引擎,以及目前热门的人工智能机器学习都使用到树,例如决策树(Decision Tree)和随机森林(Random Forest),而AVL平衡树和伸展树是二叉树的优化版。树的实现原理算法比较复杂,即使能借助图片理解,算法代码依然比较困难,在第一节中(算法分析和算法设计)有详细提到算法设计的规则,使用自然语言或流程图,或者使用伪代码也可以,本文使用自然语言描述算法,可结合相关的图片进行理解,建议尽可能理解相关实例代码,并自己动手写。
一、树的基本概念

你真的懂树吗(二叉树、AVL平衡二叉树、伸展树、B-树和B+树原理和实现代码详解)

文章图片
上图是一棵树,每个圆称为一个结点,最顶层的结点称为树根或根(Root),和根结点相连的结点称为根结点的儿子,以儿子为根的树称为子树,一棵树可能又0个或多个子树,子树是整棵树的局部树,最底层的结点称为树叶,树叶结点没有儿子或子树。
结点间的逻辑关系有:父亲结点(Parent Node),一个结点的上一个结点,根Root是所有子树的根的父亲;儿子结点(Child Node),一个结点的下面连线结点;兄弟结点(Sibling Node),具有相同父亲的结点。另外还有祖先结点和后代结点等,下图是对树的完整图解:
你真的懂树吗(二叉树、AVL平衡二叉树、伸展树、B-树和B+树原理和实现代码详解)

文章图片
数的深度和高度:
1、边:一个结点到父亲的连线,路径长为两个连线结点间的边数,一个结点到自身的路径长为0。
2、深度:以树根结点为起始点,从根结点到一个结点的唯一路径长,结点的深度可以衡量遍历该结点的时间复杂度,树的深度等于最深树叶的深度。
3、高度:从一个结点到最长路径树叶的路径长,以最深树叶结点为结束点,树的高度等于根的高度,一棵树的深度等于树高。
一般来说,一个结点的儿子可使用指针指定,但是儿子的指针是如何指定的呢?使用关键字(Key),树结点的分布依据关键字的区间划分,一般的关键字可以是字符串(根据字符串的ASCII值进行比较)或整数或浮点数,或通过合理设计可以是其它复杂的逻辑形式。根据节点的关键字,小于关键字的结点在左边,大于关键字的结点在右边。这里的关键字和数据表的唯一键或主键类似,一般来说推荐使用唯一的关键字,这样可以避免重复的结点,关键字可使用数据域中的某一成员充当,或创建一个无关的关键字(但树并不严格要求需要有关键字,也可以无关键字)。
总的来说,设计一个树ADT,其数据结构至少要包含数据域、指针域和关键字域,如下代码是一个示例:
// 数据对象,一般业务数据 typedef struct post{ unsigned int id; char *title; char *content; } Post; // 结点,包括数据域(可包含关键字),指针域 typedef struct pnode{ int key; // 可自定义创建一个无关的关键字 Post post; // 数据域(这里已包含关键字域) struct pnode *left; // 指针域,儿子结点 struct pnode *right; struct pnode *parent; struct pnode *sblings; } PNode; // 树ADT对外接口 typedef struct ptree{ PNode *root; unsigned int size; } PTree;

二、树ADT的基本实现树ADT的实现首先是数据结构的设计,其数据结构是相当简单的,像以上代码,数据结构包括数据域、关键字域和指针域,指针域包括父亲结点、一个或多个儿子结点和兄弟结点等,如下图的树,该树拥有左儿子和兄弟结点:
你真的懂树吗(二叉树、AVL平衡二叉树、伸展树、B-树和B+树原理和实现代码详解)

文章图片
不过,树的算法操作则很是复杂,最复杂的算法包括遍历、删除和平衡,这里首先介绍遍历算法,删除和平衡算法下面会介绍。树的遍历包括深度优先遍历和广度优先遍历,下图是一个二叉树的两种遍历图解(下图的数字不作为关键字,仅作为结点的编号):
你真的懂树吗(二叉树、AVL平衡二叉树、伸展树、B-树和B+树原理和实现代码详解)

文章图片
【你真的懂树吗(二叉树、AVL平衡二叉树、伸展树、B-树和B+树原理和实现代码详解)】深度优先遍历:对于遍历树结点的算法,我们只需要集中在一个根结点及其儿子结点,深度优先遍历按分支路径遍历,先按一条分支路径遍历,再遍历其它路径,根据遍历根结点的顺序有三种顺序,这三种遍历都是以根结点为中心,主要使用递归算法,在处理根结点上为具体的算法,处理子树使用递归。
先序遍历:时间复杂度为O(N),以根结点为中心,先处理根结点,再将根结点中存在的儿子结点分别取出来,儿子结点作为新的根结点,递归处理。
中序遍历:时间复杂度为O(N),以根结点为中心,从根结点取出左右儿子结点,先处理左儿子,再处理根结点,后处理右儿子,将左右儿子作为新的根结点进行递归处理。
后序遍历:时间复杂度为O(N),以根结点为中心,从根结点取出儿子结点,处理根结点,将儿子结点作为新的根结点递归处理。
深度优先遍历的实现方式有三种,递归算法,以根结点为中心进行递归遍历;迭代处理,可将递归算法转为迭代算法;借助栈进行处理,例如先序遍历的栈处理为:先将根结点入栈,出栈处理结点,将出栈的结点的儿子结点分别入栈,循环第二步。
广度优先遍历:按树的层次进行遍历,先访问第一层再访问第二层,广度优先遍历的实现方式借助队列:先将根结点入队,出队处理结点,将出队的结点的儿子分别入队,循环第二步。
下面来看看树ADT的应用,树的一个结点可以存储n个关键字及其对应的n个数据对象,以及相应的n+1个指针。树可以实现操作系统的文件系统,例如Unix/Linux或Windows,一个文件夹内有多个文件或文件夹,这里统一称为文件,即一个文件内有多个文件,一个结点有多个儿子结点,如下图:
你真的懂树吗(二叉树、AVL平衡二叉树、伸展树、B-树和B+树原理和实现代码详解)

文章图片
下面是文件系统ADT的声明代码,这里有两个树,其中一个树用于存储指针域,可以相对加快遍历儿子确定路径的速度,如果你使用的是Java或C++可以快速使用Java的treeSet和STL的set或map。
#define FILE_MAX_SIZE 10// 文件数据实体 typedef struct file{ char file_name[128]; // 关键字,同一目录中唯一 char file_content[512]; int is_directory; } File; // 文件结点 typedef struct tree Tree; typedef struct fnode{ File file; //int count; // 文件数量 //struct fnode *files[FILE_MAX_SIZE]; // 文件数组(顺序表),一个目录最多FILE_MAX_SIZE个文件, // 也可以使用链表存储,更好的方法可以使用一个二叉树存储(AVL树或伸展树,可以加快查找速度),如: Tree *files; struct fnode *parent; } FNode; // 二叉树ADT,作为一个数据容器,用于存储一个结点的所有儿子,不使用AVL平衡树或伸展树,查找速度最差的情况有可能是O(M), // M为儿子数,平均情况为O(logN) typedef struct node{ //char *file_name; // 关键字使用File中的文件名 FNode *fnode; // int fnode struct node *left; struct node *right; } Node; struct tree{ Node *root; int count; // 文件数量 }; // 文件树ADT typedef struct ftree{ FNode *root; int size; } FTree; // 二叉树ADT,数据容器 extern Tree *tree_init(); extern int tree_is_full(Tree *tree); extern int tree_is_empty(Tree *tree); extern int tree_add(Tree *tree, FNode *fnode); extern FNode *tree_search(Tree *tree, char *file_name); extern void tree_for_each(Tree *tree, void (*run)(FNode *)); extern int tree_clear(Tree *tree); // 文件树ADT extern FTree *ftree_init(); extern int ftree_is_full(FTree *ftree); extern int ftree_is_empty(FTree *ftree); extern int ftree_add(FTree *ftree, char directory[], File *file); extern int ftree_is_exist(FTree *ftree, char file_name_absolute[]); extern void ftree_traverse(FTree *ftree); extern int ftree_clear(FTree *ftree);

写完后发现使用二叉树存储指针域比较难操作,用数组会方便一点,但是效率方面要差一些,这个普通二叉树一定程度上可以加快查找速度,该文件系统项目的完整源码可到github查看:https://github.com/onnple/filesystem,源码调用例子的树结构如下图:
你真的懂树吗(二叉树、AVL平衡二叉树、伸展树、B-树和B+树原理和实现代码详解)

文章图片
三、二叉树查找树ADT1、二叉树的基本概念
上面的例子已经用到二叉树,二叉树是一种每个节点最多只有两个儿子的树,儿子的排布按照:小于关键字在左边,大于关键字在右边,二叉树是树数据结构中最简单的一种树,二叉树实质也是图,树和图都是比较复杂以及技术要求较高的数据结构。二叉树深度的平均值为O(logN),平均二叉树为根号N,这里要指出二叉树最理想的时候就是每个结点的左右子树高度相同,这个时候访问结点的最坏时间为O(logN),但是这里的二叉树并不保证要满足这个条件,加入插入关键字从1到5,就会和链表一样了,这时候时间为O(N),下面是一个普通的二叉树:
你真的懂树吗(二叉树、AVL平衡二叉树、伸展树、B-树和B+树原理和实现代码详解)

文章图片
2、二叉树的数据结构和算法
二叉树的数据结构中至少需要提供:数据域、关键字域和左右儿子指针域,假设根结点的关键字值为X,则其左子树的所有值都小于X,右子树的所有值都大于X,对于等于X的重复情况可有如下处理:
(1)可简单作替换处理,遇到重复关键字直接覆盖原值;
(2)结点增加一个数据域记录结点的重复频率;
(3)使用辅助的数据结构,例如表或二叉查找树,用另外的数据结构存储重复值。
除了重复值覆盖处理,其它两种都比较复杂,所以设计关键字要尽量是唯一的,除非有其它不同的需求。
二叉查找树的所有基本算法的平均运行时间都是O(logN),可见树或二叉树的在查找方面的效率比较好,其算法也比较复杂,其中要首先理解上面提到的两大遍历:广度优先遍历和深度优先遍历,在所有树中都可以使用。
二叉树插入数据:使用先序遍历,即先在根结点上做判断是否插入数据,后再处理左右儿子,相对没那么复杂。
二叉树查找数据:查找某个元素使用先序遍历的形式,查找最大值只需要往最右边查找,查找最小值只需要往最左边查找。
二叉树删除数据:除了上面提到的树遍历比较难之外,删除数据比遍历更复杂。对于删除所有的结点,使用后序遍历,由下至上释放数据,对于只删除一个结点的操作,有以下几种情况:
你真的懂树吗(二叉树、AVL平衡二叉树、伸展树、B-树和B+树原理和实现代码详解)

文章图片
(1)结点是树叶:直接删除本结点,然后从父结点删除该结点的指针;
(2)结点只有一个儿子:将儿子结点替换该结点;
(3)结点有两个儿子:找出该结点右子树的最小值,将最小值替换该结点,然后删除最小值所在的结点,转换成删除只有一个儿子或树结点。
具体算法为:遍历到目标结点,以该结点的右儿子为根的子树,找出该子树的最小值,用最小值替换目标结点。该算法可提高删除效率,但是上次操作会导致左子树深度比右子树深,大量删除操作会导致二叉树左移。
(4)逻辑删除:这个方式在数据表删除数据也用到,在二叉树删除中,子啊结点中添加一个频率数据域,或在节点添加删除记号。
3、二叉查找树的应用
树的应用非常广,是一个相当之有用的数据结构,除了上面提到的以及文件系统的代码实例,还有其它用处,例如排序,路由算法,语法树或表达式树、游戏场景管理或设计和图片合成等,路由算法可用于分布式服务器,游戏相关的都大量用到树或图。树的显著特点就是快速排序和快速查找,因此在使用树的时候也不必拘谨于定义, 下面举两个例子,一个是排序的简单实例,另一个是实现表达式树,表达式树又称为抽象语法树AST。
使用二叉查找树实现快速排序:因为二叉树本身就具有排序的特性,因为下面的实例不仅仅集中于排序,重点还要注意遍历、插入和删除数据,这几个都是难点,建议分析代码动手写多几次,下面是头文件二叉查找树ADT声明:
// 数据对象 typedef struct movie{ int id; // 关键字,唯一键,按id排序 char name[128]; char about[512]; } Movie; // 树结点 typedef struct mnode{ Movie movie; struct mnode *left; // 左儿子 struct mnode *right; // 右儿子 } MNode; // 二叉树ADT typedef struct stree{ MNode *root; unsigned int size; } STree; // 二叉树算法操作声明 extern STree *stree_init(); extern int stree_is_full(STree *stree); extern int stree_is_empty(STree *stree); extern MNode *stree_get_max(STree *stree); extern MNode *stree_get_min(STree *stree); extern int stree_add(STree *stree, Movie *movie); extern int stree_delete_by_id(STree *stree, int id); extern int stree_clear(STree *stree); // 排序:按id升序排列每个元素分别执行一个函数 extern void stree_process(STree *stree, void (*process)(MNode *mnode));

以上是标准的二叉查找树实现方式,完整的实现源码可以到github查看:https://github.com/onnple/stree,源码主要都是使用递归方式实现,特别要注意:实际使用时尽量或者干脆不要用递归方式写代码,递归算法会因N的变大而耗费过多内存,最好习惯使用迭代或将递归转为迭代,while或for迭代,for的方式是这样for(; ; ),迭代的检查元素主要是root根结点,之后的例子会尝试部分使用迭代。以上代码的调用实例的树形状如下:
你真的懂树吗(二叉树、AVL平衡二叉树、伸展树、B-树和B+树原理和实现代码详解)

文章图片
实现表达式树或抽象语法树BST:表达式树主要在编译器中用到,词法分析或语法分析,用于解释文本,如代码,另外最简单计算器到强大的数学计算软件都有用到,主要就是翻译文本,例如还有自然语言处理。
这里仅讨论数学表达式的计算,例如代数表达式a*b +c,转换成表达式树,其数据结构至少包含指针域,关键字域和数据域,树叶用于存储操作数,其它结点为操作符,如下图:
你真的懂树吗(二叉树、AVL平衡二叉树、伸展树、B-树和B+树原理和实现代码详解)

文章图片
表达式有三种表示方式:前缀表达式,中缀表达式和后缀表达式,分别对应三种遍历方式,我们这里只需要关注中缀表达式和后缀表达式,a×b+c则是中缀表达式,而它的后缀表达式为ab×c+,中缀表达式作为我们的书写使用习惯,但是为什么需要后缀表达式呢?因为后缀表达式方便我们构造树,也方便计算,例如ab×c+,将a和b分别入栈,遇到运算符将栈中的两个元素弹出运算,将结果压入栈。所以我们的整体逻辑是:将中缀表达式转为后缀表达式,后缀表达式转为表达式树,进行数学运算的时候使用后缀遍历,所有转换或运算都需要借用栈。下面说明一下这两种转换的算法:
中缀表达式转为后缀表达式:以运算符优先级为依据,遇到操作数输出,遇到运算符压入栈,如果发现栈顶的运算符优先级大于当前运算符,则弹出栈中的所有运算符到输出,括号运算符(只有遇到成对)才全部弹出,一直弹到(,括号()不放到输出中。
后缀表达式转为表达式树:将操作符和操作数的结点地址压入栈中,遇到操作数入栈,遇到操作符将操作数弹出作为操作符的右左儿子结点,将操作符地址入栈,最后一个操作符为根结点。
这里的实例为简单起见仅仅是实现一个二叉表达式树,程序的一个参考的完整设计流程如下:
你真的懂树吗(二叉树、AVL平衡二叉树、伸展树、B-树和B+树原理和实现代码详解)

文章图片
由于对表达式的词法分析和语法分析比较复杂,这里从简,只做简单的语法检查,下面是表达式树ADT的声明代码,其中有对表达式规则的说明:
/** * 表达式:-30.ax^2.5+3x - 5b * 表达式规则:a^0-64.a.b4 * 1、运算符仅限于+ - * / ^ ( ),(字符还包括小数点.) * 2、代数式只能使用数字和字母,(字符、数字、运算符、小数点、空格) * 3、数字可使用正负数、整数和浮点数,字母只可使用"单字符"作为标识符,空格分隔表示相乘, * 例如ab表现和a b表示a*b,数字和字符相连表示相乘,如3a/a3=3*a,数字和数字空格表示相乘3 5=3*5 * *//** * 词法分析: 字符流转为记号流(token) * 语法分析:输出抽象语法树 * 处理流程: * 1、语法规则: *非法字符 *全为字符、数字、运算符、小数点、空格,或组合,错误 *()配对 *小数点.配对:数字和小数点.的组合中只能有一个小数点,以小数点开头表示纯小数,如.5表示0.5,数字后面的小数点属于数字本身 *字母和字母间的小数点,错误 *连续重复的运算符,错误 *尾部运算符,错误 * 2、初步转化: *将字母和字母、字母和数字、数字和数字之间的空格用*替换; *去除所有空格 * 3、转换成后缀表达式 * 4、生成表达式树: *先分词,转换成一个个token * */#define TOKEN_MAX 16// 单项式 typedef struct monomial{ int priority; // 数字的优先级为-1,字母为0,()为20,+-为13,*/为14,^为15 char token[TOKEN_MAX]; } Monomial; // 表达式树结点 typedef struct enode{ Monomial monomial; struct enode *left; struct enode *right; } ENode; typedef int Cell; typedef struct cnode{ Cell cell; struct cnode *next; struct cnode *prev; } CNode; // 表达式树ADT typedef struct exp{ ENode *root; unsigned int size; } Exp; // 栈ADT typedef struct cstack{ CNode *head; CNode *tail; unsigned int size; } CStack; // 算法操作声明 extern CStack *cstack_init(); extern int cstack_push(CStack *cstack, Cell cell); extern Cell cstack_pop(CStack *cstack); extern Cell cstack_peek(CStack *cstack); extern int cstack_clear(CStack *cstack); extern Exp *exp_init(); extern int exp_load(Exp *exp, char str[]); //extern int exp_add(Exp *exp, Monomial *monomial); extern void exp_traverse(Exp *exp); extern int exp_clear(Exp *exp);

以上实现表达式树的程序中重点是利用了栈,完整实现代码可到github上查看:https://github.com/onnple/expression_tree,该程序使用了两次栈,在树数据结构上面,使用栈和队列会比较方便。
四、AVL平衡二叉树1、AVL平衡二叉树基本的概念
AVL树是一种自平衡树,它也是一个二叉树,所有树都是基于二叉树的概念,下面讨论的树,都是最基本二叉树的扩展。平衡二叉树相比普通二叉树,普通二叉树是不要求结点平均分布,最差的情况会造成O(N)的运行时间,如下图:
你真的懂树吗(二叉树、AVL平衡二叉树、伸展树、B-树和B+树原理和实现代码详解)

文章图片
这就体现不到二叉树的查找优点了,为了解决这个问题,我们需要对二叉树的构造有所要求,最理想的情况就是要求一个结点的左右子树的高度相同,但是这个要求太严格,因此我们要求每个结点的左右子树的高度最多相差1,这样AVL树可以保证最坏情况为O(logN)。
AVL树在实现上需要在每个结点中保留高度信息,或者使用平衡因子(Balanced Factor),简称BF,每个结点的平衡因子等于左子树的高度减去右子树的高度,因此平衡值只有三种-1,+1和0。AVL树主要是在增加或删除结点后需要重新计算平衡因子,调整树的结构使其重新平衡,下面是一个例子,将2插入3的左边会造成结点4和结点5失衡:
你真的懂树吗(二叉树、AVL平衡二叉树、伸展树、B-树和B+树原理和实现代码详解)

文章图片
让AVL树重新平衡的操作叫做旋转(Rotate),旋转操作是树的基本操作也是其中一个难点,对于旋转,使用结点上下移动反而会好理解一点,失衡结点的BF为2或-2,注意这个失衡结点一般取的是最小失衡结点,如上图取的是结点4,因为高度的计算是从该结点到最深子树的路径长,所以将失衡结点下移一层即可达到平衡,如下图,每一层的左右结点作为空穴,作为结点上下移动可被占据的位置。
你真的懂树吗(二叉树、AVL平衡二叉树、伸展树、B-树和B+树原理和实现代码详解)

文章图片
2、二叉树不平衡的四种情况
你真的懂树吗(二叉树、AVL平衡二叉树、伸展树、B-树和B+树原理和实现代码详解)

文章图片
首先要确定中心结点,即最小失衡结点A,其平衡因子的绝对值为2,主要有四种不平衡的情况:
(1)在A的左儿子B的左子树插入,又称为LL;
(2)在A的左儿子C的右子树插入P,又称为LR;
(3)在A的右儿子C的左子树插入P,又称为RL;
(4)在A的右儿子B的右子树插入,又称为RR。
要记住两个重要节点,一个是失衡结点,另一个是失衡结点的儿子,该儿子在失衡路径上,旋转操作则是依据失衡结点的儿子为中心,对失衡结点进行下移动。在这四种失衡情况中(1)和(4)是一样的,(2)和(3)是一样的,前者使用单旋转,后者使用双旋转。
3、AVL树单旋转和双旋转
在进行旋转操作时,首先要找到最小失衡结点,判断失衡的类型,然后选择旋转的类型,如何判断呢?根据上面的图片中的结点A,BF为2确定为左儿子左边L,根据左儿子的BF为-1,则确定为R,此时属于不平衡情况(2),使用双旋转,下面详细介绍单旋转和双旋转的四种旋转方式。
(1)LL右旋转
你真的懂树吗(二叉树、AVL平衡二叉树、伸展树、B-树和B+树原理和实现代码详解)

文章图片
P下移,占据C的右儿子空穴,C的右儿子称为P的左儿子。
(2)RR左旋转
你真的懂树吗(二叉树、AVL平衡二叉树、伸展树、B-树和B+树原理和实现代码详解)

文章图片
P下移,占据C的左儿子空穴,C的左儿子作为P的右儿子。
(3)LR左右旋转
你真的懂树吗(二叉树、AVL平衡二叉树、伸展树、B-树和B+树原理和实现代码详解)

文章图片
双旋转分为两步:左旋转,以P的儿子C作为失衡结点,Q的右儿子q,Q下移,占据q的左儿子,q的左儿子左儿子作为Q的右儿子,q作为P的左儿子。
右旋转,P下移,作为p的右儿子,q的右儿子作为P的左儿子。
(4)RL右左旋转
你真的懂树吗(二叉树、AVL平衡二叉树、伸展树、B-树和B+树原理和实现代码详解)

文章图片
右旋转,P的右儿子C作为新的失衡结点Q,Q的左儿子q,Q下移,作为q的右儿子,q的右儿子作为Q的左儿子,q作为P的右儿子。
左旋转,P下移,占据q的左儿子,q的左儿子作为P的右儿子。
4、AVL平衡二叉树的数据结构和算法实例
平衡旋转操作主要是增加数据和删除数据的时候进行,代码实现上,其数据结构需要包含数据域,指针域,包括左右儿子或父亲结点,关键字域,用于排列结点,结点高度或平衡因子BF,空树的高度为-1,叶子结点的高度为0。
下面是AVL树的ADT声明:
// 数据对象 typedef struct user{ unsigned int id; // 关键字 char username[128]; char password[128]; } User; // 结点 typedef struct avlnode{ User user; // 数据域 struct avlnode *left; // 左右儿子 struct avlnode *right; int height; // 高度 } AVLNode; // AVL树ADT对外接口 typedef struct avltree{ AVLNode *root; unsigned int size; } AVLTree; // 算法声明 extern AVLTree *avltree_init(); extern int avltree_is_full(AVLTree *avltree); extern int avltree_is_empty(AVLTree *avltree); extern int avltree_add(AVLTree *avltree, User *user); extern int avltree_delete_by_id(AVLTree *avltree, unsigned int id); extern AVLNode *avltree_get_by_id(AVLTree *avltree, unsigned int id); extern void avltree_traverse(AVLTree *avltree, void (*traverse)(AVLNode*)); extern int avltree_clear(AVLTree *avltree);

完整代码可以到github查看:https://github.com/onnple/AVLTree,平衡二叉树的实现难点在于旋转,在该实例代码中,在进行删除和添加结点经过的路径上的每个结点检查高度,发现失衡结点进行旋转,并对每个结点进行高度更新,同样,在参与旋转结点中也需要对结点进行高度更新,其中代码调用实例的例子树结构如下图:
你真的懂树吗(二叉树、AVL平衡二叉树、伸展树、B-树和B+树原理和实现代码详解)

文章图片
五、伸展树(Splay Tree)1、伸展树的基本概念
AVL树在每次删除或添加结点时都需要使用旋转操作平衡二叉树,以获得最好的查找效率,伸展树是另一种二叉树,它不需要高度或平衡因子这些平衡信息。伸展树使用另一种方式实现高效率的查找,不平衡但要求每次操作的那个结点旋转到根结点上来,这样下次查找它就能达到最快效率了,这是根据计算机的局部原理,当一块数据被访问后,此后段时间内也会该数据或附近的数据也会被再次用到。这也就是说,进行增加、删除、查找等操作都需要将本次操作的结点或附近结点旋转到根结点上,可对所有操作都调整,或只针对查找进行调整。
伸展树进行M次操作,其时间复杂度为O(M logN),而普通二叉树最坏情况为O(N),连续M次操作为O(M*N)。如果一个算法M次操作的时间为O(MF(N)),则O(F(N))称为该算法的摊还时间或摊还代价,伸展树的摊还代价为O(logN)。
2、伸展树的实现原理
综上,伸展树不需要AVL树的平衡信息,高度或BF,它是一个普通二叉查找树,它的出发点是:频繁查找一个深结点X,会造成花费的时间过多,采取的办法是:将树在X处展开,将该结点旋转到根结点,自下向上单旋转,对访问路径上的每个结点和父结点进行单旋转,这样频繁访问结点即可大大减少时间,但是执行M次操作仍然至少需要M*N的时间(最坏情况单链表为N)。
伸展树在实现上可使用上面说的单旋转,根据目标结点,全部使用单旋转,但是效率并不好,例如单链表的情况,依次插入1、2、3、4、5,其效率并不好,结点4深度依然比较深,如下图:
你真的懂树吗(二叉树、AVL平衡二叉树、伸展树、B-树和B+树原理和实现代码详解)

文章图片
为了解决这个问题,我们采取一种特别的实现,根据三种情况进行旋转:
(1)当前结点只有父亲结点,使用单旋转,很明显这种情况的父亲结点为根结点;
(2)当前结点有父亲结点和祖父结点,呈之字形,例如当前结点是父亲结点的右儿子,父亲结点是祖父结点的左儿子。之字形的情况进行一次AVL双旋转,如下图:
你真的懂树吗(二叉树、AVL平衡二叉树、伸展树、B-树和B+树原理和实现代码详解)

文章图片
(3)当前结点有父亲结点和祖父结点,呈一字形,也就是类似LL和RR的情况,但是并不是使用单旋转,而是进行一字形对称旋转。假设祖父结点是根结点,那么让当前结点X成为根结点,父亲结点称为X的右儿子,祖父结点成为父亲结点的右儿子,X的原右儿子成为父亲的左儿子,父亲结点的右儿子成为祖父结点的左儿子,下图是一个例子:
你真的懂树吗(二叉树、AVL平衡二叉树、伸展树、B-树和B+树原理和实现代码详解)

文章图片
相对于仅仅使用单旋转,新实现方法的效率更高,使用新的旋转方式,对1、2、3、4、5的单链表情况在5处展开的过程如下图:
你真的懂树吗(二叉树、AVL平衡二叉树、伸展树、B-树和B+树原理和实现代码详解)

文章图片
3、伸展树的数据结构和算法实现
伸展树的数据结构和普通二叉树的一样,至少提供指针域、数据域和关键字,而算法操作的实现稍微不同:
(1)对于增加、修改或查找结点数据,只要求将该目标结点上推到根结点;
(2)删除结点的操作为:将该删除的目标结点上推到根结点,删除根结点,此时分成了左右子树,接着找到左子树的最大结点,上推该结点为左子树的根,此时左子树没有右儿子,将右子树作为左子树的右儿子。
下面是伸展树ADT声明代码:
// 数据对象 typedef struct series{ unsigned int id; char title[128]; char introduction[256]; } Series; // 结点 typedef struct splaynode{ Series series; struct splaynode *left; struct splaynode *right; } SplayNode; // 伸展树ADT对外接口 typedef struct splaytree{ SplayNode *root; unsigned int size; } SplayTree; // 算法声明 extern SplayTree *splaytree_init(); extern int splaytree_is_full(SplayTree *splaytree); extern int splaytree_is_empty(SplayTree *splaytree); extern int splaytree_add(SplayTree *splaytree, Series *series); extern int splaytree_delete_by_id(SplayTree *splaytree, unsigned int id); extern SplayNode *splaytree_get_by_id(SplayTree *splaytree, unsigned int id); extern void splaytree_traverse(SplayTree *splaytree, void (*traverse)(SplayNode*)); extern int splaytree_clear(SplayTree *splaytree);

伸展树的重要操作是将目标结点提升为根结点,相对于AVL平衡树稍微简单,在删除数据上也比普通二叉树的删除操作简单,旋转是树的最基本操作,因此保证能掌握好旋转操作,结合普通二叉树的算法操作,旋转操作只是在每个结点上进行检查以进行旋转,该伸展树完整源码可查考github项目地址:https://github.com/onnple/splaystree,下图是该项目初始化的树结构:
你真的懂树吗(二叉树、AVL平衡二叉树、伸展树、B-树和B+树原理和实现代码详解)

文章图片
六、B-树(B-Tree)1、B-树的基本概念
B-树和下面的B+树是相当有用和比较重要的树数据结构(B-树和B树的叫法是一样的),应用于涉及硬盘数据的大量数据查找操作的场景。B-树也是一种平衡树,称为M路平衡查找树,M=2就是平衡二叉查找树,M称为阶数或度数或叉数或最多子树数,指的是一个结点拥有最多的儿子数。上面一直提到关键字域,关键字用于确定结点的分布规则,又称为键值,和数据库表的主键和唯一键是一样的。1个关键字最多有2个儿子,如二叉树,M阶平衡树的关键字数为M-1,在B-树的数据结构实现上,主要是使用关键字数M-1,可使用数组存储,或设计其它的容器如链式数据结构,其中3阶B树又叫2-3树,4阶B树又叫2-3-4树,如下图是一个3阶B叉树:
你真的懂树吗(二叉树、AVL平衡二叉树、伸展树、B-树和B+树原理和实现代码详解)

文章图片
B-树的主要特性如下:
(1)每个结点的儿子数为2~M,为什么不是至少1个?因为B树的生长方向是自底向上,在分裂的时候不会造成只有1个儿子,为什么最大为M?因为阶数为M为最大儿子数,其关键字数最大为M-1;
(2)非根非叶子结点的儿子数为[M/2]~M,[]为向上取整,或使用ceil()函数,这个不用太注意,实际上只要你正确操作B树不会发生异常的情况;
(3)所有树叶的深度都相同,这就是说B树总是平衡的。
首先要指出,以上B-树只是一个参考的规范并不是绝对标准,你可以根据自己的需求自己设计,这里的M一直指的都是每个结点的最大儿子数,而在我们的代码中更直接的是使用关键字数,关键字数等于M-1,要注意是否混淆了。
B树的主要数据存储在所有结点上,和一般的二叉树是一样的,在二叉树上一个关键字对应一个数据对象,B树中H个关键字对应有H个数据对象,也就是说关键字和数据对象的数量是相同的。如果使用的是数据对象中的成员作为数据关键字,则在节点中可以直接声明一个数据对象的数组存储(或者其它类型的容器),否则自定义创建一个关键字数组,另外再创建数据对象数组,这样会相当麻烦(实际可以在数据对象中创建虚拟关键字,在结点声明)。
数据库索引:这里简单介绍一下数据库索引的概念,何为索引?关键字的集合就是索引了,实际上在线性表中的关键字也可以统称索引,但是我们说索引一般是和“高速“相关的,二叉树的所有关键字就是高速索引的例子,平衡树二叉树最坏情况也是O(logN),索引可以使用数字或字符串,这个上面已经说过了,这个和MySQL等数据库中的概念是一样的。
和索引对应的就是数据对象或数据对象的地址,都是和关键字保存在一个结点中,这样如果一个结点过大,那么进行查找时IO操作次数就会多,例如一次IO最大访问数据量为Q,包含10个结点,如果没查找继续读取,但是如果一次把索引读出找到结点,再读取结点,这样两步就完成,后面介绍的B+树就可以实现这样的操作。
B树的最大深度为[log N],底数为M/2,最坏运行时间为O(M logN),底数为M,M为阶数,一般来说M=3或4时最好,当需要存储大量数据时,M可取值范围为:32< =M< =256,在结点上使用二分法查找时间为O(log M),查找结点时间为O(logN),其中M的选择应尽可能至少使得一个内部结点能装进一个磁盘块的最大值,假如一个结点大小大于磁盘块而加入一次IO只读取一个磁盘块,那么读取一个结点就要进行两次IO操作,相对于磁盘来说IO操作是一种实际的机械运动。
2、B-树的数据结构和算法设计
(1)B-树数据结构B树的数据结构设计中,一般包含数据域,可存储实际的数据对象或数据对象的地址,关键字域,指针域,详细的结点信息包括:
父亲结点指针,方便在进行结点分裂或合并时操作;
关键字数量和关键字集,关键字使用升序排列;
儿子结点集,儿子结点的数量最大为M;
另外可选的信息包括:是否为叶子结点,数据域在数据库中存储的是数据的逻辑地址,在数据库中,一行称为一条记录(Record),一条记录包括了关键字(主键),数据域(其它字段数据),又可看作键值对。
数组长度可全部设定为M,对于关键字数组,多出一个位置可用于存储产生分裂的中结点,这里也可以将关键字和结点的左指针存储在数据对象中。
(2)B-树算法操作B-树的操作算法中的难点也是插入和删除操作,下面先介绍B-树的插入操作:
你真的懂树吗(二叉树、AVL平衡二叉树、伸展树、B-树和B+树原理和实现代码详解)

文章图片
插入操作实际也并不是很难,就像上面的表达式树一样,描述起来可能有些复杂,但实现上并不复杂,插入过程如下:
设关键字数为K,关键字数组的大小为M,若K < M-1,即当前结点关键字数K小于最大的关键字数,则直接插入,一般插入需要重新排列;
若K == M-1,插入到关键字数组,此时数组大小为M,以第[M/2]个关键字为中心,将关键字数组分成左右两部分,即左右分裂成两个结点;
此时将第[M/2]个关键字插入到父结点,若当前结点没有父结点,则新建一个作为父结点,第[M/2]个关键字的左右儿子为分裂出来的左右两个结点。
其中有一个优化的方式是:按需插入数据,只要有合适的位置即插入,如上面的图片中9可以直接插入到3后面,此时就需要检查儿子结点的关键字数是否已满。
B-树删除操作:
你真的懂树吗(二叉树、AVL平衡二叉树、伸展树、B-树和B+树原理和实现代码详解)

文章图片
删除索引结点(内部结点):使用右子树中最小的关键字进行覆盖(或左子树最大的关键字),再删除子树中的关键字,递归检查叶子结点。
删除叶子结点:没找到对应关键字结束删除,若找到则删除,设Q=[M/2]-1,若当前结点关键字数K> =Q,结束删除;
若K< Q,访问附近的兄弟结点,若兄弟结点的关键字数k> =Q,从兄弟借一个关键字:父结点关键字下移到当前结点,兄弟结点上移成为父结点,结束删除;若兄弟结点k< Q,将当前结点、父结点和兄弟结点合并。
综上,B-树插入数据空间满则分裂,删除数据不够则借或合并兄弟结点。
3、B-树数据结构和算法源码具体实现
B-树相对于普通的二叉树实现比较复杂,只要理解好,那么树这个数据结构就能掌握好了,树是难点而且也是相对有用的,先看下面的B-树ADT声明代码:
// 阶数或度数 #define DEGREE 3// 数据表的一行记录,业务数据 typedef struct post{ unsigned int id; // 关键字 char title[128]; char content[256]; } Post; // B树结点,DEGREE阶B树,DEGREE-1个关键字,DEGREE个儿子,关键字使用多一个位置用于保存溢出的关键字 typedef struct bnode{ unsigned int leaf; // 是否是叶子 unsigned int size; // 关键字数量/记录数量 //int keys[M_MAX]; // 关键字域,这里使用数据记录中的关键字,这样会比较好操作 Post *posts[DEGREE]; // 数据记录集(Records),B树的主要特点是数据记录存储在所有结点 struct bnode *children[DEGREE]; // 儿子结点集 struct bnode *parent; // 父结点 } BNode; // 查找结果集 typedef struct resultset{ unsigned int size; unsigned int id; Post *posts[]; // 结果记录 } ResultSet; // B树ADT对外接口 typedef struct btree{ BNode *root; unsigned int size; } BTree; // 算法声明 extern BTree *btree_init(); extern int btree_is_full(BTree *btree); extern int btree_is_empty(BTree *btree); extern int btree_add(BTree *btree, Post *post); extern int btree_delete_by_id(BTree *btree, unsigned int id); extern Post *btree_get_by_id(BTree *btree, unsigned int id); extern void btree_traverse(BTree *btree, void(*traverse)(Post*)); extern int btree_clear(BTree *btree);

以上实现B-树的完整源码可到github上查看https://github.com/onnple/b-tree,该项目删除元素时是有些问题的,如发现望指正,另外,该项目值得参考,但是实现效果并不是很好,下面介绍B+树的内容,和B树是相似的,相关实现源码留待下一节提供。
七、B+树(B+Tree)B树和B+树的主要应用在于数据库开发,例如MySQL的索引引擎就是使用B+树实现的,如此看来,使用数据库的目的除了数据持久化就是索引了,如果数据库失去了索引功能,那么和一般的文件访问也就区别不大了。说到数据库,这里稍微讨论一下相关的内容,数据库文件是存储在硬盘上的,程序访问数据需要调用外设硬件去读取硬盘上的数据,一次读取操作称为一次IO操作,IO操作是比较耗时的,因此提高数据访问的速度也就是要降低IO操作的次数。
相对于物理磁盘而言,数据的最小单位为扇区,一般512字节,相对文件系统而言,一次IO操作读取的数据大小目前可达到4K,也就是8个扇区。假如一个结点为4K,N个结点,最多深度为O(log N),底数为M/2,加入一个结点存储200个关键字,一百万个结点只需读取几次即可,而关键字的查询速度也是对数时间O(log M),如此你可以发现使用B树或B+树的功能强大。
1、B+树基本概念
B+树和B树的定义是等价的,其中有的定义是儿子数比关键字数小1,这个不是很重要,完全可以自定义。和B树不同的是B+树主要分为索引结点和叶子结点,索引结点为内部结点,主要用于存储关键字,不再存储数据,这样一个索引结点的空间就小多了(一次IO操作可以读取更多的关键字),叶子节点是数据记录存储的地方。索引结点中的关键字按升序排列。另外和B树主要不同的是,B+树每个叶子结点保存相邻叶子结点的指针(双向链表),这样因为叶子结点中的关键字也是按升序排列的,那么B+树不仅可以提供随机访问,还可以进行范围访问,因此使用B+树实现索引引擎会比B树更有优势。
注意,只有叶子结点才存储实际数据,MySQL的InnoDB引擎直接在叶子结点存储数据本身,而MyISAM引擎则是在叶子结点存储数据的逻辑地址,前者的方式称为聚簇索引,后者称为非聚簇索引,下面是这两种索引结构的粗略图:
你真的懂树吗(二叉树、AVL平衡二叉树、伸展树、B-树和B+树原理和实现代码详解)

文章图片
2、B+树的插入操作和删除操作
(1)B+树插入操作
你真的懂树吗(二叉树、AVL平衡二叉树、伸展树、B-树和B+树原理和实现代码详解)

文章图片
空树或结点未满,直接插入;
对于索引结点,先插入关键字到结点中,关键字树为K:
K < = M-1,插入结束;
K > M-1,分裂结点,分成左右两个结点,以[M/2]个关键字为中心,该结点进入父结点,中心关键字分到右边,右边部分的中心关键字不去除(非叶子结点在右边部分则不保留中心关键字)。
对于叶子结点,先插入关键字到结点中,K < = M-1,插入结束;
K > M-1,分裂结点,分成左右两部分,以第[M/2]个关键字为中心(非叶子结点不保留中心关键字)。
以上操作均为递归操作,往父结点添加关键字同样需要重新检查K的大小。
(2)B+树删除操作
你真的懂树吗(二叉树、AVL平衡二叉树、伸展树、B-树和B+树原理和实现代码详解)

文章图片
设Q=[M/2]-1,对于叶子结点:
没有对应的关键字,结束删除;
有对应关键字,关键数K > =Q,结束删除;
K < Q,检查兄弟结点的关键字k,k> Q,借兄弟结点的关键字;k< =Q,合并当前结点、父亲结点和兄弟结点的关键字。
对于B+树的实现源码,因为比较复杂,下一节再详细讨论。

    推荐阅读