当前课程知识点：数据结构（Data Structures） > 3. Tree > 3.4 Binary Search Tree > Video
返回《数据结构（Data Structures）》慕课在线视频课程列表
返回《数据结构（Data Structures）》慕课在线视频列表
在这节课中我们将学习到一种
支持高效数据查找操作的二叉树
二叉查找树
英文叫做Binary Search Tree
我们先来看一下二叉查找树它的定义
二叉查找树简称为BST
它是一种特殊的二叉树
对树上的值等于K的每个结点来说
它的左子树上的所有结点的值都会小于K
而右子树上所有结点的值都会大于等于K
比如在这个例子里面根结点它的值是37
那么它的左子树里面
所有结点的值都会小于37
而右子树上面
所有结点的值会大于等于37
除了树根之外
树里面的每一个结点都有类似的性质
左子树上的结点要小于当前结点的值
而右子树上的结点
要大于等于当前结点的值
二叉查找树上的这些特殊的性质
使得在树中去查找特定的值会十分的高效
比如在这个例子里面我们要查找32
去判断在树里面是否存在32
那么我们将从树根开始从上往下查找
首先 我们会把32和树根进行比较
因为32小于树根37
那么根据二叉查找树的性质
小于37的结点只能存在37的左子树中
所以我们将继续在左子树里面查找
因此我们将左子树的树根结点24
继续和我们要找的32进行比较
因为32相对来说比较大
所以我们将继续在24的右子树里面
来进行查找
直到我们在最后面的叶子结点
找到了这个32
纵观整个查找的过程
就是沿着从树根到树上的某个结点的
一条路径上的查找过程
所以在这个过程中访问过的结点的数目
它不会超过整个树的高度
而树的高度往往是远远地小于
树上的结点总数 n的
因此 在二叉查找树上面查找特定的值
它的效率要远远地高于θ(n)
所以给定一组数据
如果我们可以想办法
把它组织成为一个二叉查找树的话
那么将可以支持在这组数据中的快速查找
下面我们将讨论如何去实现二叉查找树
二叉查找树它本质上也是二叉树的一种
所以二叉查找树它的存储结构
和二叉树的结构是一样的
所以类似于二叉树的类的定义
我们也可以以同样的方法
去定义一个二叉查找树BST类
类里面有一个核心成员
就是一个指向树根的指针 root
好的 我们这节课就讲到这里
下节课我们再见
-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
