当前课程知识点：数据结构（Data Structures） > 5. Index > 5.4 Implementation of 2-3 tree > Video
返回《数据结构（Data Structures）》慕课在线视频课程列表
返回《数据结构（Data Structures）》慕课在线视频列表
各位同学大家好
下面我们将学习到2-3树的实现过程
我们先来回顾一下2-3树的结构
2-3树它本质上也是树的一种特殊形式
在树上面每个结点它最多存放2个关键字
最多有3个孩子
我们在实现2-3树的时候
重点需要定义好这个2-3树的结点结构
我们来看一下2-3树的结点的定义
在这里面我们定义了两个模板参数
一个是用来去表示关键字类型的Key
另外一个是数据元素的内容Elem
我们来看一看结点内TTNode的定义
首先在结点中最多包含有2个关键字
所以我们定义了左关键字 lkey
和右关键字 rkey
同时我们定义了
和关键字相关的数据元素 le和re
这些数据元素可以用来去存放
任何和关键字相关联的信息
比如说关键字对应的记录
存放在磁盘中的位置
另外 每个结点最多有三个孩子
所以我们还需要去定义
三个分别指向这三个孩子结点的指针
从左往右依次是left center还有right
那么基于前面的这个结点类TTNode
我们就可以去实现2-3树类TTTree
在这个类的定义里面最核心的属性成员
是一个指向树根结点的指针 root
类似于我们前面所学习到二叉树的实现
所有的针对这棵树的操作
我们都将从树根开始 从上往下来进行
下面我们来看一下
如何在2-3树上面去实现一个查找操作
我们先来定义一下函数的原型
Search参数
这个函数有三个参数
第一个是指向树根的指针 root
第二个是我们要查找的关键字 Key
第三个是一个引用参数 e
用来去记录我们查找到的数据元素
我们前面学习过
在2-3树上面
进行查找关键字Key的时候
也就是要把Key和树根结点的关键字
进行比较
然后决定继续在哪个指数里面进行查找
这个过程是一个递归嵌套的过程
在把Key和树根的关键字进行比较之后
这个问题就转变成为
对其中的一棵子树的递归查找过程
随着递归调用的进行
问题的规模会不断地变小
直到查找过程结束
下面我们来看一下具体的实现
在和树根进行比较之前
我们首先要判断一下树根是不是存在的
如果不存在说明它是一棵空树
马上返回false 停止查找
如果树根它不是空的
我们就把Key和树根的左关键字进行比较
如果Key等于左关键字
那么我们就将对应的数据元素
le进行返回
记录在引用参数e中 成功停止查找
另外一种情况就是
如果Key和树根的右关键字相等
那么我们将把相应的数据元素re进行返回
如果树根的关键字跟Key都不相等
那么我们就需要
进一步地到指数里面去查找
这个时候我们根据Key的值
来去决定在哪个指数里面进行查找
如果Key小于左关键字
那么显然 Key只能存在于左指数里面
所以我们继续在左指数中查找
所以我们递归地去调用Serch参数
第一个参数里面传递的是
左指数的树根指针
也就是树根的左孩子指针
剩下的几种情况
都是Key大于左关键字的情况
如果树根它只有两个孩子
也就是右孩子指针为空的情况下
那么Key只会存在于中间的指数里面
所以我们将递归地
在中间的指数中进行查找
如果树根有三个孩子
并且Key小于右关键字
那么Key也只能存在于中间的指数
所以我们也是递归地在中间指数中
进行查找
最后一种情况也就是大于右关键字的情况
那么我们将在右指数里面进行递归查找
在这里面我们再次看到了
由于树的本身它存在着嵌套的性质
所以递归函数非常适用于各类树的操作
2-3树它也不例外
好的 我们这节课就讲到这里
下节课我们再见
-1. Introduction--1.1 Introduction of Data
-1.1 Introduction of Data Structure
--Introduction of Data Structure
-1.2 Data Structure and A
-1.2 Data Structure and Algorithm
--Video
-1.3 Asymptotic Analysis
-1.3 Asymptotic Analysis
--Video
-1.4 Simplifying Rules of
-1.4 Simplifying Rules of Asymptotic Analysis
--Video
-2.1 Introduction of List
-2.1 Introduction of List
--Video
-2.2 Array based List
-2.2 Array based List
--Video
-2.3 Insertion Operation on Array
-2.3 Insertion Operation on Array based List
--Video
-2.4 Remove Operation on Array based List
-2.4 Remove Operation on Array based List
--Video
-2.5 Linked list
-2.5 Linked list
--Video
-2.6 Insertion Operation on Linked list
-2.6 Insertion Operation on Linked list
--Video
-2.7 Remove Operation on Linked list
-2.7 Remove Operation on Linked list
--Video
-2.8 SetPos Operation on Linked list
-2.8 SetPos Operation on Linked list
--Video
-2.9 Stack
-2.9 Stack
--Video
-2.10 Application of Stack
--Video
-2.11 Queue
-2.11 Queue
--Video
-3.1 Definition of Binary Tree
-3.1 Definition of Binary Tree
--Video
-3.2 Implementation of Binary Tree
-3.2 Implementation of Binary Tree
--Video
-3.3Traversal
-3.3 Traversal
--Video
-3.4 Binary Search Tree
-3.4 Binary Search Tree
--Video
-3.5 Search on BST
-3.5 Search on BST
--Video
-3.6 Insertion on BST
-3.6 Insertion on BST
--Video
-3.7 Introduction of Heap
-3.7 Introduction of Heap
--Video
-3.8 Construction of Heap
-3.8 Construction of Heap
--Video
-3.9 Operations on Heap
--Video
-3.10 General Tree
--Video
-4.1 Definition of Searching
--Video
-4.2 Searching of Sorted Array
-4.2 Searching of Sorted Array
--Video
-4.3 Definition of Hash Table
--Video
-4.4 Collision in Hash Table
-4.4 Collision in Hash Table
--Video
-4.5 Extension of Linear Probing
--Video
-4.6 Insertion Operation of Hash Table
--Video
-4.7 Search Operation of Hash Table
-4.7 Search Operation of Hash Table
--Video
-5.1 Introduction of Index
--Video
-5.2 Linear Index
-5.2 Linear Index
--Video
-5.3 2-3 tree index
-5.3 2-3 tree index
--Video
-5.4 Implementation of 2-3 tree
-5.4 Implementation of 2-3 tree
--Video
-5.5 B-Tree
-5.5 B-Tree
--Video
-5.6 Insertion Operation on B+ Tree
--Video
-5.7 Deletion Operation on B+ Tree
--Video
-6.1 Definition of Graph
--Video
-6.2 Implementation of Graph
--Video
-6.3 Adjacency Matrix
--Video
-6.4 Adjacency List
--Video
-6.5 Graph Traversal - DFS
--Video
-6.6 Graph Traversal - BFS
--Video
-6.7 Topological Sort
--Video
-6.8 Shortest Path Problem
--Video
-6.9 Single Source Shortest Path
--Video
-6.10 Dijkstra Algorithm
--Video
-7.1 Sorting Problem
--Video
-7.2 Insertion Sort
--Video
-7.3 Selection Sort
--Video
-7.4 Bubble Sort
--Video
-7.5 Shell Sort
--Video
-7.6 Quick Sort
--Video
-7.7 Heap Sort
--Video
-7.8 Comparison
--Video
