当前课程知识点：数据结构（Data Structures） > 3. Tree > 3.6 Insertion on BST > Video
返回《数据结构（Data Structures）》慕课在线视频课程列表
返回《数据结构（Data Structures）》慕课在线视频列表
大家好
在这节课中我们将学习到
在二叉查找树上面的插入操作
我们先来看一个具体的例子
在这棵二叉查找树上面我们要插入35
如果我们要插入新的结点
我们就必须要在这棵上面
去查找一个合适的插入位置
所以我们首先要在里面
执行一个查找的过程
我们首先把35和树根进行比较
因为35要小于树根37
所以我们继续在左子树里面去查找
类似于二叉查找树的查找过程
最终这个查找将终止于叶子结点32
35最终将会插入到32的右子树里面去
整个过程是从树根开始
而树上的结点不断地比较的过程
下面我们来看一下插入操作的实现
这里的Insert函数
第一个参数是树根结点的指针
第二个参数是我们要插入的数据元素
整个函数会返回插入元素之后
这个树的树根指针
插入的过程中
我们首先要去判断树根是否是空的
如果这个树是一个空树
我们将创建一个新的结点
结点的内容会去存放我们插入的数据元素
如果树根不是空的
那么我们将会把要插入的e
和树根进行比较
如果e是比树根的值小
那么我们将把e
插入到树根的左子树里面去
所以这里面
我们递归地去调用Insert函数
其中函数的第一个参数
是左子树的树根指针
也就是树根的左孩子指针
而第二个参数就是我们要插入的数据元素
这个函数将会返回
插入之后左子树的树根指针
在这里我们可以看到
我们重新设置了树根的左孩子指针
让这个指针重新指向左子树的树根
之所以我们要这样做
是因为如果原来左子树是空的
那么往里面插入一个结点之后
这个结点将会变成新的左子树树根
所以我们需要重新去设置一下
原来树根的左孩子
我们让这个左孩子指针
指向新插入的树根结点
最后一个分支是
插入的元素e大于等于树根的情况
那这种情况下
我们将会把e插入到树根的右子树里面去
在函数结束之前
我们要返回指向树根的指针
最终完成这个插入的操作
下面我们来看一下
在BST上面进行插入操作的代价
因为这个插入过程和查找的过程是相似的
所以它们具有相似的时间复杂度
最好的情况下如果我们插入的位置
是在根结点的孩子位置
那么这个插入过程可以很快的
在常数时间内完成
那最差的情况下
这个BST退化成为一个线性的结构
那么在这种极端的情况下
算法复杂度类似于在链表中插入一个结点
这种情况它的时间复杂度是θ(n)
下面我们来分析一下
对于一棵平衡二叉查找树来说
在上面进行插入操作的平均代价
类似于BST的查找操作
在BST上面插入一个结点的代价
它是取决于这棵树的高度的
这个过程是一个从树根开始
终止于树上的某个结点的过程
所以插入数据它的平均代价也是θ(log n)
好的 这节课我们就讲到这里
下节课我们再见
-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
