二叉搜索树简介说明
下文笔者讲述二叉搜索树的简介说明,如下所示
二叉搜索树的简介
二叉搜索树:
是一种数据结构
用于存储数据并支持快速的插入、删除和搜索操作
二叉搜索树是一种树形结构
二叉搜索树的特点
1.每个节点最多有两个子节点
分别称为左子节点和右子节点。
2.对于每个节点，其左子节点的值小于该节点的值
右子节点的值大于该节点的值
3.中序遍历二叉搜索树可以得到有序的元素序列。
由于二叉树的某些特性导致
二叉搜索树在插入、删除和搜索操作上具有较高的效率
在平均情况下，这些操作的时间复杂度为 O(log n)
其中 n 为树中节点的数量
然而，如果树的结构不平衡
最坏情况下这些操作的时间复杂度可能会达到 O(n)
由于其高效的搜索特性
二叉搜索树常被用于实现关联数组和集合等数据结构
为了避免树的结构不平衡导致性能下降，人们也发展了平衡二叉搜索树（如红黑树、AVL树）等变种
二叉搜索树的成员变量及其构造方法
外部类成员变量有：根节点、节点类（内部类）。 外部类构造方法：默认的构造方法，对外公开二叉搜索树的核心方法。 节点类的成员变量有： key 关键字：相对比一般的二叉树 二叉搜索树可以明显提高增删查改的效率原因在于关键字 可以根据比较两个关键字的大小进行操作 value 值：作用则为存放值。 left ：链接左节点。 right：链接右节点。 节点类的构造方法： 带两个参数的构造方法：参数为 key 、value 带四个参数的构造方法：参数为 key 、value 、left 、right例:代码示例
public class BinaryTree {
BinaryNode root = null;
static class BinaryNode {
int key;
Object value;
BinaryNode left;
BinaryNode right;
public BinaryNode(int kty, Object value) {
this.key = kty;
this.value = value;
}
public BinaryNode(int key, Object value, BinaryNode left, BinaryNode right) {
this.key = key;
this.value = value;
this.left = left;
this.right = right;
}
}
}
实现二叉树的核心接口
public interface BinarySearchTreeInterface {
/**
*查找 key 对应的 value
*/
Object get(int key);
/**
* 查找最小关键字对应值
*/
Object min();
/**
* 查找最大关键字对应值
*/
Object max();
/**
* 存储关键字与对应值
*/
void put(int key, Object value);
/**
* 查找关键字的后驱
*/
Object successor(int key);
/**
* 查找关键字的前驱
*/
Object predecessor(int key);
/**
* 根据关键字删除
*/
Object delete(int key);
}
实现二叉搜索树 - 获取值 get(int key)
从根节点开始
先判断当前的节点 p.key 与 key 进行比较
当p.key > key，则向左子树下潜 p = p.left ；
当p.key < key ，则向右子树下潜 p = p.right ；
当p.key == key ，则找到到了关键字，返回该节点的值 p.value
按这样的规则一直循环下去，直到 p == null 退出循环，则说明没有找到对应的节点，则返回 null 。
例
@Override
public Object get(int key) {
if (root == null) {
return null;
}
BinaryNode p = root;
while(p != null) {
if (p.key > key) {
p = p.left;
}else if (p.key < key) {
p = p.right;
}else {
return p.value;
}
}
return null;
}
二叉搜索树 - 获取最小的关键字min(BinaryNode node)
在某一个树中
需要得到最小的关键字
由根据数据结构的特点，最小的关键字在数的最左边
实现思路:
一直向左子树遍历下去
直到 p.left == null时
则该p节点就是最小的关键字
然后找到了最小的节点，返回该节点的值即可
例
非递归实现：
@Override
public Object min() {
if (root == null) {
return null;
}
BinaryNode p = root;
while(p.left != null) {
p = p.left;
}
return p.value;
}
//重载了一个方法，带参数的方法。
public Object min(BinaryNode node) {
if (node == null) {
return null;
}
BinaryNode p = node;
while (p.left != null) {
p = p.left;
}
return p.value;
}
递归实现：
//使用递归实现找最小关键字
public Object minRecursion() {
return doMin(root);
}
private Object doMin(BinaryNode node) {
if (node == null) {
return null;
}
if (node.left == null) {
return node.value;
}
return doMin(node.left);
}
二叉搜索树 - 获取最大的关键字 max(BinaryNode node)
在某一个树中，需要得到最大的关键字
根据数据结构的特点，最大的关键字在数的最右边
实现思路:
一直向右子树遍历下去，直到 p.right == null 时
则该 p 节点就是最大的关键字了
然后找到了最大的节点，返回该节点的值即可。
例
非递归实现：
@Override
public Object max() {
if (root == null) {
return null;
}
BinaryNode p = root;
while(p.right != null) {
p = p.right;
}
return p.value;
}
//重载了一个带参数的方法
public Object max(BinaryNode node) {
if (node == null) {
return null;
}
BinaryNode p = node;
while (p.right != null) {
p = p.right;
}
return p.value;
}
递归实现：
//使用递归实现找最大关键字
public Object maxRecursion() {
return doMax(root);
}
private Object doMax(BinaryNode node) {
if (node == null) {
return null;
}
if (node.right == null) {
return node.value;
}
return doMax(node.right);
}
二叉搜索树 - 增、更新 put( int key, Object value)
在二叉搜索树中
先试着查找是否存在与key对应的节点p.key
当找到时
则为更新该值 p.value = value 即可
当找不到，则需要新增该关键字节点
例
@Override
public void put(int key, Object value) {
if (root == null) {
root = new BinaryNode(key,value);
return;
}
BinaryNode p = root;
BinaryNode parent = null;
while (p != null) {
parent = p;
if (p.key > key) {
p = p.left;
} else if (p.key < key) {
p = p.right;
}else {
p.value = value;
return;
}
}
//该树没有该关键字，因此需要新建节点对象
BinaryNode newNode = new BinaryNode(key,value);
if (newNode.key < parent.key) {
parent.left = newNode;
}else {
parent.right = newNode;
}
}
二叉搜索树 - 查找关键字的后驱节点 successor(int key)
实现思路:
先遍历找到该关键字的节点
若找不到，则返回 null
若找到了，判断以下的两种情况
第一种情况：该节点有右子树，则该关键字的后驱为右子树的最小关键字
第二种情况：该节点没有右子树，则该关键字的后驱为从右向左而来的祖宗节点
最后返回该后驱节点的值
例
@Override
public Object successor(int key) {
if (root == null) {
return null;
}
//先找到该关键字节点
BinaryNode p = root;
BinaryNode sParent = null;
while (p != null) {
if (p.key > key) {
sParent = p;
p = p.left;
} else if (p.key < key) {
p = p.right;
}else {
break;
}
}
//没有找到关键字的情况
if (p == null) {
return null;
}
//情况一:该节点存在右子树,则该后继为右子树的最小关键字
if (p.right != null) {
return min(p.right);
}
//情况二:该节点不存在右子树，那么该后继就需要到祖宗从右向左的节点
if (sParent == null) {
//可能不存在后继节点,比如最大关键字的节点就没有后继节点了
return null;
}
return sParent.value;
}
二叉搜索树 - 查找关键字的前驱节点 predecessor(int key)
实现思路:
先对该二叉树进行遍历寻找 key 的节点
若遍历结束还没找到，则返回 null
若找到了，需要判断以下两种情况：
第一种情况：该节点有左子树，则该前驱节点为该左子树的最大关键字节点
第二种情况：该节点没有左子树，则该前驱节点为从左向右而来的祖宗节点
最后返回该前驱节点的值
例
@Override
public Object predecessor(int key) {
if (root == null) {
return null;
}
BinaryNode p = root;
BinaryNode sParent = null;
while (p != null) {
if (p.key > key) {
p = p.left;
} else if (p.key < key) {
sParent = p;
p = p.right;
}else {
break;
}
}
if (p == null) {
return null;
}
//情况一:存在左子树，则该前任就为左子树的最大关键字节点
if (p.left != null) {
return max(p.left);
}
//情况二:不存在左子树，则该前任为从祖宗自左向右而来的节点
if (sParent == null) {
return null;
}
return sParent.value;
}
二叉搜索树 - 删除关键字节点 delete(int key)
实现思路:
先遍历二叉树，查找该关键字节点
若遍历结束了还没有找到，则返回 null
若找到了，则需要以下四种情况：
第一种情况：找到该删除的节点只有左子树。则直接让该左子树 "托付" 给删除节点的双亲节点，
这就删除了该节点了。至于左子树是链接到双亲节点的左边还有右边这个问题，根据该数据结构的特点，
由该删除节点来决定。若删除的节点之前是链接该双亲节点的左边，则左子树也是链接到该双亲节点的左边；
若删除的节点之前是链接该双亲节点的右边，则左子树也是链接到该双亲节点的右边。
第二种情况：找到该删除的节点只有右子树。则直接让该右子树 "托付" 给删除节点的双亲节点，
这就删除了该节点了。至于右子树是链接到双亲节点的左边还有右边这个问题，
根据该数据结构的特点，由该删除节点来决定。若删除的节点之前是链接该双亲节点的左边，
则右子树也是链接到该双亲节点的左边；若删除的节点之前是链接该双亲节点的右边，
则右子树也是链接到该双亲节点的右边。
第三种情况：找到该删除节点都没有左右子树。
该情况可以归并到以上两种情况的任意一种处理均可。
第四种情况：找到该删除节点都有左右子树
分两步：
第一步，先找后继节点来替换删除节点，找该后继节点直接到删除节点的右子树中找最小的关键字节点即可
第二步，需要先将后继节点的右子树处理好，需要将该右子树交给替换节点的双亲节点链接
还需要判断两种情况：
第一种情况:若删除节点与替换节点是紧挨着的，对替换节点的右子树无需要求，
只对左子树重新赋值；
第二种情况:若删除节点与替换节点不是紧挨着的关系，对替换节点的左右子树都要重新赋值。
例
@Override
public Object delete(int key) {
if (root == null) {
return null;
}
BinaryNode p = root;
BinaryNode parent = null;
while (p != null) {
if (p.key > key) {
parent = p;
p = p.left;
} else if (p.key < key) {
parent = p;
p = p.right;
}else {
break;
}
}
//没有找到该关键字的节点
if (p == null) {
return null;
}
//情况一、二、三:只有左子树或者右子树或者都没有
if (p.right == null) {
shift(parent,p,p.left);
} else if (p.left == null) {
shift(parent,p,p.right);
}else {
//情况四:有左右子树
//替换节点采用删除节点的后继节点
//先看被删的节点与替换的节点是否为紧挨在一起
BinaryNode s = p.right;
BinaryNode sParent = p;
while (s.left != null) {
sParent = s;
s = s.left;
}
if (sParent != p) {
//说明没有紧挨在一起，则需要将替换节点的右子树进行处理
shift(sParent,s,s.right);
s.right = p.right;
}
shift(parent,p,s);
s.left = p.left;
}
return p.value;
}
private void shift(BinaryNode parent, BinaryNode delete, BinaryNode next) {
if (parent == null) {
root = next;
} else if (parent.left == delete) {
parent.left = next;
}else if (parent.right == delete){
parent.right = next;
}
}
//使用递归实现删除关键字节点
public BinaryNode deleteRecursion(BinaryNode node , int key) {
if (node == null) {
return null;
}
if (node.key > key) {
node.left = deleteRecursion(node.left,key);
return node;
} else if (node.key < key) {
node.right = deleteRecursion(node.right,key);
return node;
}else {
if (node.right == null) {
return node.left;
} else if (node.left == null) {
return node.right;
}else {
BinaryNode s = node.right;
while (s.left != null) {
s = s.left;
}
s.right = deleteRecursion(node.right,s.key);
s.left = node.left;
return s;
}
}
}
二叉搜索树 - 查找范围小于关键字的节点值 less(int key)
实现思路:
使用中序遍历，来遍历每一个节点的 key
若小于 key 的节点，直接放到数组容器中
若大于 key 的，可以直接退出循环。最后返回该数组容器即可。
例
//找 < key 的所有 value
public list<Object> less(int key) {
if (root == null) {
return null;
}
ArrayList<Object> result = new ArrayList<>();
BinaryNode p = root;
Stack<BinaryNode> stack = new Stack<>();
while (p != null || !stack.isEmpty()) {
if (p != null) {
stack.push(p);
p = p.left;
}else {
BinaryNode pop = stack.pop();
if (pop.key < key) {
result.add(pop.value);
}else {
break;
}
p = pop.right;
}
}
return result;
}
二叉搜索树 - 查找范围大于关键字的节点值 greater(int key)
实现思路
使用中序遍历
遍历每一个节点的 key
若大于 key 的节点，直接放到数组容器中
例
//找 > key 的所有 value
public List<Object> greater(int key) {
if (root == null) {
return null;
}
ArrayList<Object> result = new ArrayList<>();
Stack<BinaryNode> stack = new Stack<>();
BinaryNode p = root;
while (p != null || !stack.isEmpty()) {
if (p != null) {
stack.push(p);
p = p.left;
}else {
BinaryNode pop = stack.pop();
if (pop.key > key) {
result.add(pop.value);
}
p = pop.right;
}
}
return result;
}
方法优化:
遍历方向进行调整
先从右子树开始，再访问根节点，最后才到左子树
因此只要小于 key 的关键字节点，直接退出循环
例
//改进思路:遍历方向进行调整，先从右子树开始，再访问根节点，最后才到左子树
public List<Object> greater1(int key) {
if (root == null) {
return null;
}
ArrayList<Object> result = new ArrayList<>();
Stack<BinaryNode> stack = new Stack<>();
BinaryNode p = root;
while (p != null || !stack.isEmpty()) {
if (p != null ) {
stack.push(p);
p = p.right;
}else {
BinaryNode pop = stack.pop();
if (pop.key > key) {
result.add(pop.value);
}else {
break;
}
p = pop.left;
}
}
return result;
}
二叉搜索树 - 查找范围大于 k1 且小于 k2 关键字的节点值 between(int k1, int k2)
实现思路:
同上
注意事项:
当前节点的 key > k2 ,则可以退出循环
例
//找到 >= k1 且 =< k2 的所有value
public List<Object> between(int k1, int k2) {
if (root == null) {
return null;
}
ArrayList<Object> result = new ArrayList<>();
Stack<BinaryNode> stack = new Stack<>();
BinaryNode p = root;
while(p != null || !stack.isEmpty()) {
if (p != null) {
stack.push(p);
p = p.left;
}else {
BinaryNode pop = stack.pop();
if (pop.key >= k1 && pop.key <= k2) {
result.add(pop.value);
} else if (pop.key > k2) {
break;
}
p = pop.right;
}
}
return result;
}
二叉搜索树完整代码示例
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;
public class BinaryTree implements BinarySearchTreeInterface{
BinaryNode root = null;
static class BinaryNode {
int key;
Object value;
BinaryNode left;
BinaryNode right;
public BinaryNode(int kty, Object value) {
this.key = kty;
this.value = value;
}
public BinaryNode(int key, Object value, BinaryNode left, BinaryNode right) {
this.key = key;
this.value = value;
this.left = left;
this.right = right;
}
}
@Override
public Object get(int key) {
if (root == null) {
return null;
}
BinaryNode p = root;
while(p != null) {
if (p.key > key) {
p = p.left;
}else if (p.key < key) {
p = p.right;
}else {
return p.value;
}
}
return null;
}
@Override
public Object min() {
if (root == null) {
return null;
}
BinaryNode p = root;
while(p.left != null) {
p = p.left;
}
return p.value;
}
public Object min(BinaryNode node) {
if (node == null) {
return null;
}
BinaryNode p = node;
while (p.left != null) {
p = p.left;
}
return p.value;
}
//使用递归实现找最小关键字
public Object minRecursion() {
return doMin(root);
}
private Object doMin(BinaryNode node) {
if (node == null) {
return null;
}
if (node.left == null) {
return node.value;
}
return doMin(node.left);
}
@Override
public Object max() {
if (root == null) {
return null;
}
BinaryNode p = root;
while(p.right != null) {
p = p.right;
}
return p.value;
}
public Object max(BinaryNode node) {
if (node == null) {
return null;
}
BinaryNode p = node;
while (p.right != null) {
p = p.right;
}
return p.value;
}
//使用递归实现找最大关键字
public Object maxRecursion() {
return doMax(root);
}
private Object doMax(BinaryNode node) {
if (node == null) {
return null;
}
if (node.right == null) {
return node.value;
}
return doMax(node.right);
}
@Override
public void put(int key, Object value) {
if (root == null) {
root = new BinaryNode(key,value);
return;
}
BinaryNode p = root;
BinaryNode parent = null;
while (p != null) {
parent = p;
if (p.key > key) {
p = p.left;
} else if (p.key < key) {
p = p.right;
}else {
p.value = value;
return;
}
}
//该树没有该关键字，因此需要新建节点对象
BinaryNode newNode = new BinaryNode(key,value);
if (newNode.key < parent.key) {
parent.left = newNode;
}else {
parent.right = newNode;
}
}
@Override
public Object successor(int key) {
if (root == null) {
return null;
}
//先找到该关键字节点
BinaryNode p = root;
BinaryNode sParent = null;
while (p != null) {
if (p.key > key) {
sParent = p;
p = p.left;
} else if (p.key < key) {
p = p.right;
}else {
break;
}
}
//没有找到关键字的情况
if (p == null) {
return null;
}
//情况一:该节点存在右子树,则该后继为右子树的最小关键字
if (p.right != null) {
return min(p.right);
}
//情况二:该节点不存在右子树，那么该后继就需要到祖宗从右向左的节点
if (sParent == null) {
//可能不存在后继节点,比如最大关键字的节点就没有后继节点了
return null;
}
return sParent.value;
}
@Override
public Object predecessor(int key) {
if (root == null) {
return null;
}
BinaryNode p = root;
BinaryNode sParent = null;
while (p != null) {
if (p.key > key) {
p = p.left;
} else if (p.key < key) {
sParent = p;
p = p.right;
}else {
break;
}
}
if (p == null) {
return null;
}
//情况一:存在左子树，则该前任就为左子树的最大关键字节点
if (p.left != null) {
return max(p.left);
}
//情况二:不存在左子树，则该前任为从祖宗自左向右而来的节点
if (sParent == null) {
return null;
}
return sParent.value;
}
@Override
public Object delete(int key) {
if (root == null) {
return null;
}
BinaryNode p = root;
BinaryNode parent = null;
while (p != null) {
if (p.key > key) {
parent = p;
p = p.left;
} else if (p.key < key) {
parent = p;
p = p.right;
}else {
break;
}
}
//没有找到该关键字的节点
if (p == null) {
return null;
}
//情况一、二、三:只有左子树或者右子树或者都没有
if (p.right == null) {
shift(parent,p,p.left);
} else if (p.left == null) {
shift(parent,p,p.right);
}else {
//情况四:有左右子树
//替换节点采用删除节点的后继节点
//先看被删的节点与替换的节点是否为紧挨在一起
BinaryNode s = p.right;
BinaryNode sParent = p;
while (s.left != null) {
sParent = s;
s = s.left;
}
if (sParent != p) {
//说明没有紧挨在一起，则需要将替换节点的右子树进行处理
shift(sParent,s,s.right);
s.right = p.right;
}
shift(parent,p,s);
s.left = p.left;
}
return p.value;
}
private void shift(BinaryNode parent, BinaryNode delete, BinaryNode next) {
if (parent == null) {
root = next;
} else if (parent.left == delete) {
parent.left = next;
}else if (parent.right == delete){
parent.right = next;
}
}
//使用递归实现删除关键字节点
public BinaryNode deleteRecursion(BinaryNode node , int key) {
if (node == null) {
return null;
}
if (node.key > key) {
node.left = deleteRecursion(node.left,key);
return node;
} else if (node.key < key) {
node.right = deleteRecursion(node.right,key);
return node;
}else {
if (node.right == null) {
return node.left;
} else if (node.left == null) {
return node.right;
}else {
BinaryNode s = node.right;
while (s.left != null) {
s = s.left;
}
s.right = deleteRecursion(node.right,s.key);
s.left = node.left;
return s;
}
}
}
//找 < key 的所有 value
public List<Object> less(int key) {
if (root == null) {
return null;
}
ArrayList<Object> result = new ArrayList<>();
BinaryNode p = root;
Stack<BinaryNode> stack = new Stack<>();
while (p != null || !stack.isEmpty()) {
if (p != null) {
stack.push(p);
p = p.left;
}else {
BinaryNode pop = stack.pop();
if (pop.key < key) {
result.add(pop.value);
}else {
break;
}
p = pop.right;
}
}
return result;
}
//找 > key 的所有 value
public List<Object> greater(int key) {
if (root == null) {
return null;
}
ArrayList<Object> result = new ArrayList<>();
Stack<BinaryNode> stack = new Stack<>();
BinaryNode p = root;
while (p != null || !stack.isEmpty()) {
if (p != null) {
stack.push(p);
p = p.left;
}else {
BinaryNode pop = stack.pop();
if (pop.key > key) {
result.add(pop.value);
}
p = pop.right;
}
}
return result;
}
//改进思路:遍历方向进行调整，先从右子树开始，再访问根节点，最后才到左子树
public List<Object> greater1(int key) {
if (root == null) {
return null;
}
ArrayList<Object> result = new ArrayList<>();
Stack<BinaryNode> stack = new Stack<>();
BinaryNode p = root;
while (p != null || !stack.isEmpty()) {
if (p != null ) {
stack.push(p);
p = p.right;
}else {
BinaryNode pop = stack.pop();
if (pop.key > key) {
result.add(pop.value);
}else {
break;
}
p = pop.left;
}
}
return result;
}
//找到 >= k1 且 =< k2 的所有value
public List<Object> between(int k1, int k2) {
if (root == null) {
return null;
}
ArrayList<Object> result = new ArrayList<>();
Stack<BinaryNode> stack = new Stack<>();
BinaryNode p = root;
while(p != null || !stack.isEmpty()) {
if (p != null) {
stack.push(p);
p = p.left;
}else {
BinaryNode pop = stack.pop();
if (pop.key >= k1 && pop.key <= k2) {
result.add(pop.value);
} else if (pop.key > k2) {
break;
}
p = pop.right;
}
}
return result;
}
}
版权声明
本文仅代表作者观点，不代表本站立场。
本文系作者授权发表，未经许可，不得转载。
