当前课程知识点：数据结构（Data Structures） > 3. Tree > 3.5 Search on BST > Video
返回《数据结构（Data Structures）》慕课在线视频课程列表
返回《数据结构（Data Structures）》慕课在线视频列表
在这节课中我们将学习
在二叉查找树上面的查找操作
我们这里定义 find的函数
来去实现这样的一个查找操作
函数有两个参数
一个是指向树根的指针 root
一个是我们要查找的元素 e
这个查找的过程
我们首先要去判断树根是否为空的
如果我们遇到空的树根
那么就要返回false
表示查找失败
否则我们要把查找的元素e
和树根进行比较
如果e小于树根
那么我们将在树根的左子树上面
进一步地去查找
在这个子树上面的查找过程
它是一个递归的过程
所以我们将在这里
递归地调用find的函数
而函数的第一个参数是左子树的树根指针
第二个参数是我们要查找的元素e
如果e 比这个树根的值要大
那么我们会有另外的一种情况
我们将在树根的右子树上面
做进一步地查找
最后如果e和树根的值是相等的这种情况
就表示查找成功 返回true
下面我们来分析一下
在二叉查找树上面的查找操作的效率
最好的情况下如果我们要找的元素
刚好就是这个二叉查找树的树根结点
那么整个查找过程可以在常数时间内完成
所以它的复杂度是θ(1)
而在最差的情况下
如果二叉查找树变成下面这样的极端情况
所有结点由小到大的
排列成为一个线性结构
在这种情况下从树根开始去查找一个结点
它的算法复杂度
将和在链表中进行查找的复杂度是相当的
都是θ(n)
为了提高查找效率我们应当尽可能地避免
让这个二叉查找树
退化成为一个不平衡的状态
我们应当尽可能地让二叉查找树保持平衡
那么二叉查找树的
最佳状态是怎么样子的呢
就是这里我们所看到的平衡二叉查找树
在这棵树上面
任何一个结点
它的左子树的高度和右子树的高度
相差不会超过1
目前 有一些成熟的算法
是可以保证在二叉查找树的构建过程中
能让它始终保持平衡
感兴趣的同学
可以在附件的材料中
找到相关的内容来进行自学
那么我们来分析一下
对于一棵平衡的二叉查找树来说
在上面进行查找操作的平均代价是多少呢
这个代价取决于整个树的高度
我们可以证明一棵平衡二叉查找树
它的平均高度是等于θ(log n)的
所以在这里面进行查找
它的代价也是θ(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
