引言打算写写树形数据结构：二叉查找树、红黑树、跳表和B树。这些数据结构都是为了解决同一个基本问题：如何快速地对一个大集合执行增删改查。本篇是第一篇，讲讲搜索树的基础：二叉搜索树。基本问题如何在一千万个手机号中快速找到13012345432这个号（以及相关联信息，如号主姓名）？最笨的方案把一千万个手机号从头到尾遍历一遍，直到找到该手机号，返回对应的姓名。其时间复杂度是O(n)————当然这肯定不是我们要的方案。最秀的方案用散列表，可以在O(1)的时间复杂度完成查找。关于散列表的原理和代码参见算法（TypeScript版本）。散列表的问题散列表的查询性能非常优秀，插入和删除的性能也不赖，但它有什么
二分搜索树的特性一、顺序性二分搜索树可以当做查找表的一种实现。我们使用二分搜索树的目的是通过查找key马上得到value。minimum、maximum、successor（后继）、predecessor（前驱）、floor（地板）、ceil（天花板、rank（排名第几的元素）、select（排名第n的元素是谁）这些都是二分搜索树顺序性的表现。二、局限性二分搜索树在时间性能上是具有局限性的。如下图所示，元素节点一样，组成两种不同的二分搜索树，都是满足定义的：二叉搜索树可能退化成链表，相应的，二叉搜索树的查找操作是和这棵树的高度相关的，而此时这颗树的高度就是这颗树的节点数n，同时二叉搜索树相应的
二分搜索树的特性一、顺序性二分搜索树可以当做查找表的一种实现。我们使用二分搜索树的目的是通过查找key马上得到value。minimum、maximum、successor（后继）、predecessor（前驱）、floor（地板）、ceil（天花板、rank（排名第几的元素）、select（排名第n的元素是谁）这些都是二分搜索树顺序性的表现。二、局限性二分搜索树在时间性能上是具有局限性的。如下图所示，元素节点一样，组成两种不同的二分搜索树，都是满足定义的：二叉搜索树可能退化成链表，相应的，二叉搜索树的查找操作是和这棵树的高度相关的，而此时这颗树的高度就是这颗树的节点数n，同时二叉搜索树相应的
二分搜索树节点删除本小节介绍二分搜索树节点的删除之前，先介绍如何查找最小值和最大值，以及删除最小值和最大值。以最小值为例（最大值同理）：查找最小key值代码逻辑，往左子节点递归查找下去：...//返回以node为根的二分搜索树的最小键值所在的节点privateNodeminimum(Nodenode){ if(node.left==null) returnnode; returnminimum(node.left);}...删除二分搜索树的最小key值，如果该节点没有右子树，那么直接删除，如果存在右子树，如图所示：删除节点22，存在右孩子，只需要将右子树33节点代替节点22。这个删除
二分搜索树节点删除本小节介绍二分搜索树节点的删除之前，先介绍如何查找最小值和最大值，以及删除最小值和最大值。以最小值为例（最大值同理）：查找最小key值代码逻辑，往左子节点递归查找下去：...//返回以node为根的二分搜索树的最小键值所在的节点privateNodeminimum(Nodenode){ if(node.left==null) returnnode; returnminimum(node.left);}...删除二分搜索树的最小key值，如果该节点没有右子树，那么直接删除，如果存在右子树，如图所示：删除节点22，存在右孩子，只需要将右子树33节点代替节点22。这个删除
二分搜索树层序遍历二分搜索树的层序遍历，即逐层进行遍历，即将每层的节点存在队列当中，然后进行出队（取出节点）和入队（存入下一层的节点）的操作，以此达到遍历的目的。通过引入一个队列来支撑层序遍历：如果根节点为空，无可遍历；如果根节点不为空：先将根节点入队；只要队列不为空：出队队首节点，并遍历；如果队首节点有左孩子，将左孩子入队；如果队首节点有右孩子，将右孩子入队；下面依次演示如下步骤：（1）先取出根节点放入队列（2）取出29，左右孩子节点入队（3）队首17出队，孩子节点14、23入队。（4）31出队，孩子节点30和43入队（5）最后全部出队核心代码示例：...//二分搜索树的层序遍历public
二分搜索树层序遍历二分搜索树的层序遍历，即逐层进行遍历，即将每层的节点存在队列当中，然后进行出队（取出节点）和入队（存入下一层的节点）的操作，以此达到遍历的目的。通过引入一个队列来支撑层序遍历：如果根节点为空，无可遍历；如果根节点不为空：先将根节点入队；只要队列不为空：出队队首节点，并遍历；如果队首节点有左孩子，将左孩子入队；如果队首节点有右孩子，将右孩子入队；下面依次演示如下步骤：（1）先取出根节点放入队列（2）取出29，左右孩子节点入队（3）队首17出队，孩子节点14、23入队。（4）31出队，孩子节点30和43入队（5）最后全部出队核心代码示例：...//二分搜索树的层序遍历public
二分搜索树深度优先遍历二分搜索树遍历分为两大类，深度优先遍历和层序遍历。深度优先遍历分为三种：先序遍历（preordertreewalk）、中序遍历（inordertreewalk）、后序遍历（postordertreewalk），分别为：1、前序遍历：先访问当前节点，再依次递归访问左右子树。2、中序遍历：先递归访问左子树，再访问自身，再递归访问右子树。3、后序遍历：先递归访问左右子树，再访问自身节点。前序遍历结果图示：对应代码示例：...//对以node为根的二叉搜索树进行前序遍历,递归算法privatevoidpreOrder(Nodenode){ if(node!=null){
二分搜索树深度优先遍历二分搜索树遍历分为两大类，深度优先遍历和层序遍历。深度优先遍历分为三种：先序遍历（preordertreewalk）、中序遍历（inordertreewalk）、后序遍历（postordertreewalk），分别为：1、前序遍历：先访问当前节点，再依次递归访问左右子树。2、中序遍历：先递归访问左子树，再访问自身，再递归访问右子树。3、后序遍历：先递归访问左右子树，再访问自身节点。前序遍历结果图示：对应代码示例：...//对以node为根的二叉搜索树进行前序遍历,递归算法privatevoidpreOrder(Nodenode){ if(node!=null){
二分搜索树节点的查找二分搜索树没有下标,所以针对二分搜索树的查找操作,这里定义一个contain方法,判断二分搜索树是否包含某个元素,返回一个布尔型变量,这个查找的操作一样是一个递归的过程,具体代码实现如下:...//查看以node为根的二分搜索树中是否包含键值为key的节点,使用递归算法privatebooleancontain(Nodenode,Keykey){ if(node==null) returnfalse; if(key.compareTo(node.key)==0) returntrue; elseif(key.compareTo(node.key)0)
