【数据结构】Java实现二叉搜索树

二叉搜索树的基本性质

二叉搜索树（Binary Search Tree, BST）是一种特殊的二叉树，它具有以下特征：

1. 节点结构：每个节点包含一个键（key）和值（value），以及指向左子树和右子树的指针。

2. 左子树和右子树的性质：
   - 对于每个节点，左子树中所有节点的键都小于该节点的键。
   - 右子树中所有节点的键都大于该节点的键。
   - 这种特性使得二叉搜索树可以高效地进行查找、插入和删除操作。

3. 查找操作：从根节点开始，比较目标键与当前节点的键。如果目标键小于当前节点的键，则继续在左子树中查找；如果大于，则在右子树中查找。这个过程递归进行，直到找到目标节点或者到达树的叶子节点。

4. 插入操作：插入新节点时，同样从根节点开始，根据二叉搜索树的性质，选择左子树或右子树，直到找到一个空位置插入新节点。

5. 删除操作：删除节点较为复杂，分为三种情况：
   - 若被删除节点为叶子节点，直接移除。
   - 若被删除节点只有一个子节点，则用其子节点替代该节点。
   - 若被删除节点有两个子节点，则需要找到该节点的后继节点（通常是右子树中最小的节点），用其替代被删除的节点，并递归删除后继节点。

二叉搜索树的平均时间复杂度为O(log n)，但在最坏情况下（如插入顺序导致树变为链表），其时间复杂度可达到O(n)。为了避免这一问题，通常会使用自平衡的二叉搜索树，如红黑树或AVL树。

二叉搜索树在许多应用中非常重要，包括数据库索引、内存中的排序数据以及许多算法实现等。

代码实现二叉搜索树的基本操作

查找操作

二叉搜索树（BST）中的查找操作是基于树的特性进行的，具体原理如下：

查找操作原理

1. 初始化当前节点（cur）:

   • 将当前节点设置为树的根节点（root），开始从树的顶端进行查找。

2. 循环查找:

   • 使用while循环遍历树的节点，条件是cur不为null（即当前节点存在）。

3. 比较当前节点与目标值:

   • 左子树查找：如果当前节点的值小于目标值，说明目标值可能在右子树中，因此将cur指向cur.right。
   • 右子树查找：如果当前节点的值大于目标值，说明目标值可能在左子树中，将cur指向cur.left。
   • 找到目标值：如果当前节点的值等于目标值，则查找成功，返回true。

4. 查找结束:

   • 如果循环结束，意味着没有找到目标值，此时返回false。

代码实现：

public boolean search(int val) {// 初始化当前节点为根节点treeNode cur = root;// 当当前节点不为空时循环查找while (cur != null) {// 如果当前节点的值小于目标值，则在右子树继续查找if (cur.val < val) {cur = cur.right;// 如果当前节点的值大于目标值，则在左子树继续查找} else if (cur.val > val) {cur = cur.left;// 如果找到目标值，返回true} else {return true;}}// 如果遍历结束仍未找到目标值，返回falsereturn false;
}

查找操作利用了二叉搜索树的排序性质，能够在相对较短的时间内找到目标值。通过比较和递归向左或向右子树移动，该操作在实际应用中被广泛使用，例如在需要快速检索数据的系统中，如数据库和内存中的索引结构等。

插入操作

二叉搜索树（Binary Search Tree, BST）的插入操作是基于树的特性进行的，以下是插入操作的原理详解：

插入操作原理

1. 开始插入：

   • 从树的根节点开始进行插入操作。

2. 比较键值：

   • 对于当前节点，比较要插入的值（key）与当前节点的键（val）：
     • 如果要插入的值小于当前节点的键，则应该将其插入到左子树中。
     • 如果要插入的值大于当前节点的键，则应该将其插入到右子树中。
     • 如果要插入的值等于当前节点的键，通常视为重复值，根据具体需求，可以选择不插入、更新值或者其他处理。

3. 寻找空位：

   • 将当前节点更新为其左子树或右子树，然后重复该过程，直到找到一个空位置（即当前节点为null）。
   • 该空位置即为将新值插入树中的位置。

4. 插入新节点：

   • 在找到的空位置创建新的节点，并将其插入到树中。

 代码实现：

    public boolean insert(int val) {treeNode node = new treeNode(val);if(root == null) {root = node;return true;}treeNode cur = root;treeNode parent = null;while(cur != null) {if(val > cur.val) {parent = cur;cur = cur.right;}else if(val < cur.val) {parent = cur;cur = cur.left;}else {return false;}}if(val > parent.val) {parent.right = node;}else {parent.left = node;}return true;}

插入操作遵循了二叉搜索树的基本特性，通过比较和递归地前进来在合适的位置插入新节点。这一操作是保持树的结构的关键，确保每次插入后都能满足二叉搜索树的性质，以便后续的查找、删除等操作更加高效。

删除操作

1. 查找要删除的节点：

   • 从根节点开始，通过与当前节点的值比较，找到目标节点。如果目标值大于当前节点值则继续查找右子树；如果小于，则查找左子树。同时记录当前节点的父节点。

2. 执行删除操作：

   • 一旦找到要删除的节点，调用removeNode方法，根据要删除节点的子节点情况执行不同的删除逻辑。

代码实现：

public void remove(int key) {treeNode cur = root;        // 当前节点初始化为根节点treeNode parent = null;     // 记录当前节点的父节点// 找到要删除的节点while(cur != null) {if(key > cur.val) {parent = cur;       // 更新父节点cur = cur.right;    // 向右子树查找} else if(key < cur.val) {parent = cur;       // 更新父节点cur = cur.left;     // 向左子树查找} else {// 找到目标节点，执行删除逻辑removeNode(parent, cur);return;            // 找到并删除后退出}}System.out.println("没有该节点"); // 如果节点未找到，输出提示信息
}// 执行删除操作的方法
private void removeNode(treeNode parent, treeNode cur) {// 情况1：要删除的节点没有左子节点if(cur.left == null) {if(cur == root) {root = cur.right;  // 如果要删除的节点是根节点，更新根节点} else if(cur == parent.left) {parent.left = cur.right; // 更新父节点的左子指针} else {parent.right = cur.right; // 更新父节点的右子指针}}// 情况2：要删除的节点没有右子节点else if(cur.right == null) {if(cur == root) {root = cur.left;   // 如果要删除的节点是根节点，更新根节点} else if(cur == parent.left) {parent.left = cur.left; // 更新父节点的左子指针} else {parent.right = cur.left; // 更新父节点的右子指针}}// 情况3：要删除的节点有两个子节点else {// 找到要删除节点的右子树中的最小节点treeNode target = cur.right;treeNode targetParent = cur;// 寻找右子树中最小节点while(target.left != null) {targetParent = target; // 更新最小节点的父节点target = target.left;   // 持续向左查找}// 用找到的最小节点的值替代要删除的节点的值cur.val = target.val;// 删除最小节点if(target == targetParent.right) {targetParent.right = target.right; // 更新父节点的右子指针} else {targetParent.left = target.right;  // 更新父节点的左子指针}}
}

1. 查找节点：

   • 使用while循环查找目标节点，记录其父节点，以便于后续的删除操作。比较节点值，并依据结果移动到左或右子树。

2. 删除逻辑：

   • 没有左子节点：直接将右子节点连接到父节点，删除当前节点。
   • 没有右子节点：直接将左子节点连接到父节点，同样删除当前节点。
   • 有两个子节点：找到右子树中最小的节点（后继节点），用其值替代当前节点的值，然后递归删除后继节点。

3. 输出信息：

   • 如果在树中找不到目标节点，输出“没有该节点”提示。

性能分析

插入和删除操作都必须先查找，查找效率代表了二叉搜索树中各个操作的性能。
对有n个结点的二叉搜索树，若每个元素查找的概率相等，则二叉搜索树平均查找长度是结点在二叉搜索树的深度的函数，即结点越深，则比较次数越多。
但对于同一个关键码集合，如果各关键码插入的次序不同，可能得到不同结构的二叉搜索树：

最优情况下，二叉搜索树为完全二叉树，其平均比较次数为：
最差情况下，二叉搜索树退化为单支树，其平均比较次数为：