二叉搜索树是一种基础性的数据结构，可用于构建更为抽象的数据结构，如集合、多重集、关联数组等。
定义
二叉搜索树（Binary Search Tree，简称BST），也称有序二叉树或排序二叉树，它是一种具有如下特性的二叉树：
- 在节点左子树中，任意一个节点都小于该节点
- 在节点右子树中，任意一个节点都大于该节点
即，设x是二叉搜索树中的一个节点，如果y是x左子树中的一个结点，那么y.key < x.key；如果y是x右子树中的一个节点，那么y.key > x.key。
而根据此定义我们不难得出以下结论：
- 二叉搜索树的最小元素，处于树的最左侧
- 二叉搜索树的最大元素，处于树的最右侧
因此，在代码实现上（对于最大值与最小值的实现）我们可以像以下这样：
/**
* 获取二叉搜索树最小值
* @param node 根节点
* @return node
*/
public Node getMinNode(Node node){
while(node.left!=null){
node = node.left;
}
return node;
}
/**
* 获取二叉搜索树最大值
* @param node 根节点
* @return node
*/
public Node getMaxNode(Node node){
while(node.right != null){
node = node.right;
}
return node;
}
操作
二叉搜索树的操作主要包括查找、插入和删除，它们的时间复杂度与树的高度成正相关，即操作时间复杂度为O(h)（其中h为树的高度）。如果在树的高度平衡的情况下可得h=logn（其中n为节点个数），即操作时间复杂度变为O(logn)；而如果在最差情况下高度不平衡的树会演变为链表，即操作时间复杂度变为O(n)。
查找元素
在二叉搜索树中查找元素存在两种方式，分别是递归搜索和迭代搜索。但是两者本质上是相同的，即从根节点开始（root）执行以下流程：
- 如果节点等于
null则表示搜索的key不存在于树中并返回 - 如果节点等于搜索的
key则表示查找成功并返回 - 如果节点小于搜索的
key则表示搜索的key在其右子树中，所以进一步搜索右子树（二叉搜索树性质） - 如果节点大于搜索的
key则表示搜索的key在其左子树中，所以进一步搜索左子树（二叉搜索树性质）
/**
* 查找树 --用递归实现
*
* @param node 当前根节点
* @param key 搜索的元素
* @return node
*/
public Node search(Node node, int key) {
//递归终点，找到或者找不到
if (node == null || key == node.key) {
return node;
}
if (node.key > key) {
return search(node.left, key);
}else{
return search(node.right, key);
}
}
/**
* 查找树 --用迭代实现 ，迭代版本高效一点
*
* @param node 当前根节点
* @param key 搜索的元素
* @return node
*/
public Node iteractiveSearch(Node node, int key) {
while (node != null && key != node.key) {
if (node.key > key){
node = node.left;
}else {
node = node.right;
}
}
return node;
}
插入元素
二叉搜索树的插入是基于查找操作进行的，即从根节点开始查找插入节点的父节点（通过查找算法遍历到节点为null为止），然后进行赋值。
/**
* 插入数据
*
* @param root 根结点
* @param key 数据
* @return node
*/
public Node insert(Node root , int key){
Node p = null;
// 寻找插入节点的父节点
while(root != null){
p = root;
if (root.key > key){
root = root.left;
}else {
root = root.right;
}
}
// 创建插入节点
root = new Node();
root.val = key;
root.parent = p;
root.left = null;
root.right = null;
// 如果当前节点不是root节点（如果为root节点则变量p不会被赋值）
if(p != null){
if(key < p.val){
p.left = root;
}else{
p.right = root;
}
}
//返回插入的结点
return root;
}
删除元素
同理，对于二叉搜索树的删除也是基于查找操作进行的，即从根节点开始查找出删除节点并将其删除。不过，对于删除节点存在一个额外的步骤：对节点删除后二叉搜索树的修复。
为了更好理解二叉搜索树节点删除后的修复操作，我们先来了解一下二叉搜索树的两个概念，分别是前驱结点和后继结点：
- 前驱结点：在
val值比当前节点小的节点中，val值最大的节点 - 后继节点：在
val值比当前节点大的节点中，val值最小的节点
如果我们对二叉搜索树通过中序遍历返回节点列表，不难得出当前节点的前驱节点即是其数组索引前一个元素，而后继节点则是其数组索取的后一个元素。
当然，我们是不可能通过这种方式获取其前驱节点或后继节点，因为这样做效率太低了。但我们可以借鉴中序遍历的算法来实现其前驱节点或后继节点的获取，代码如下所示：
/**
* 获取后继结点
*
* @param node 当前结点
* @return node
*/
public Node getSuccessor(Node node){
//右子树不为空
if (node.right != null){
return getMinNode(node.right);
}
//取其父结点
Node parent = node.parent;
//判断该结点在父结点的左边还是右边，循环直到左边
while(parent!=null && parent.right == node){
node = parent;
parent = parent.parent;
}
//返回后继结点
return parent;
}
/**
* 获取前驱结点
*
* @param node 当前结点
* @return node
*/
public Node getPredecessor(Node node){
//左子树不为空
if (node.left != null){
return getMaxNode(node.left);
}
//取其父结点
Node parent = node.parent;
//判断该结点在父结点的左边还是右边，循环直到右边
while(parent!=null && parent.left == node){
node = parent;
parent = parent.parent;
}
//返回前驱结点
return parent;
}
在了解完二叉搜索树的前驱节点和后继节点后，我们再来看看关于删除操作的具体操作，这里主要分为2个步骤：
- 通过查找算法找到需要删除的节点（如无则返回）
- 对删除节点进行删除（通过修改节点间的引用关系）
- 如果删除节点不存在左子树，则直接将其右子树移植到删除节点的位置
- 如果删除节点不存在右子树，则直接将其左子树移植到删除节点的位置
- 如果删除节点同时存在左右子树，则将其后继节点移植到删除节点的位置（此处需要注意，移植后继节点前必须对其后继节点进行清理，即将后继节点的子树移植到它的位置上）
/**
* 删除结点
*
* @param root 根结点
* @param key 删除的key
*/
public void delete(Node root, int key) {
// 寻找需删除的节点
Node node = searchDeleteNode(root, key);
// 如果存在删除节点则真正执行删除
if(node != null){
doDelete(root,node);
}
}
public void searchDeleteNode(Node root, int key){
Node node = null;
// 寻找需删除的节点
for(Node tmp = root ; tmp != null ;){
if (tmp.key > key){
tmp = tmp.left;
}else if(tmp.key < key){
tmp = tmp.right;
}else{
node = tmp;
}
}
return node;
}
public void doDelete(Node root, Node node) {
// 如果删除节点的左子树为null，则直接用右子树代替
if(node.left == null){
// 将右子树移植到删除节点node处
transplant(root, node, node.right);
// 如果删除节点的右子树为null，则直接用左子树代替
}else if(node.right == null){
// 将左子树移植到删除节点node处
transplant(root, node, node.left);
// 如果删除节点的左子树与右子树都不为null
}else{
// 获取后继节点，因为此处左右子树都不为空，所有后继节点肯定在右子树中
Node successor = getSuccessor(node);
// 如果后继节点并非删除节点的直接子节点，则需要先对后继节点进行清理处理
if (successor.parent != node) {
// 将后继节点的右子树移植到后继节点处
transplant(root, successor, successor.right);
successor.right = node.right;
successor.right.parent = successor;
}
// 将后继节点移植到删除节点node处
transplant(root, node, successor);
// 处理存在的左子树
successor.left = node.left;
successor.left.parent = successor;
}
}
/**
* 将replace节点移植到node节点处
* 主要通过修改node节点与其父结点的指向关系
*
* @param root 根结点
* @param node 要删除的结点
* @param replace 替换到删除结点位置的结点
*/
private void transplant(Node root, Node node, Node replace) {
//如果node结点为根结点
if (node.parent == null) {
root = replace;
//如果node结点为其父结点的左子树
} else if (node == node.parent.left) {
node.parent.left = replace;
//如果node结点为其父结点的右子树
} else {
node.parent.right = replace;
}
// 修改replace节点的父节点引用
if (replace != null) {
replace.parent = node.parent;
}
}
扩展
- 中序遍历：先遍历其左子树，然后遍历当前节点，最后遍历其右子树（当前节点的遍历处于左右子树之间，顾名思义称之为中序遍历）
- 先序遍历：先遍历当前节点，然后遍历其左子树，最后遍历其右子树（当前节点的遍历处于左右子树之前，顾名思义称之为先序遍历）
- 后序遍历：先遍历其左子树，然后遍历其右子树，最后遍历当前节点（当前节点的遍历处于左右子树之后，顾名思义称之为后序遍历）
/**
* 中序遍历
*
* @param root 根结点
*/
public void inorder(Node root) {
if (root != null) {
inorder(root.left);
System.out.print(root.key + " ");
inorder(root.right);
}
}
/**
* 先序遍历
*
* @param root 根结点
*/
public void preorder(Node root) {
if (root != null) {
System.out.print(root.key + " ");
preorder(root.left);
preorder(root.right);
}
}
/**
* 后序遍历
*
* @param root 根结点
*/
public void postrder(Node root) {
if (root != null) {
postrder(root.left);
postrder(root.right);
System.out.print(root.key + " ");
}
}
参考
- 算法导论《二叉搜索树》
- Wiki《Binary search tree》
评论区