MapSet之二叉搜索树

系列文章：

                 1.   先导片--Map&Set之二叉搜索树

                 2.   Map&Set之相关概念

目录

前言

1.二叉搜索树

1.1 定义

1.2 操作-查找

1.3 操作-新增

1.4 操作-删除(难点)

1.5 总体实现代码

1.6 性能分析

---

前言

      TreeMap 和 TreeSet 是 Java 中基于搜索树实现的 Map 和 Set。实际上，它们使用的是红黑树数据结构，而红黑树是一种近似平衡的二叉搜索树。在红黑树的基础上，还添加了颜色属性以及红黑树性质验证来确保树的平衡性，所以我们需要了解一下二叉搜索树这个概念。

1.二叉搜索树

1.1 定义

二叉搜索树又称二叉排序树，它或者是一棵空树，或者是具有以下性质的二叉树 :

若它的左子树不为空，则左子树上所有节点的值都小于根节点的值

若它的右子树不为空，则右子树上所有节点的值都大于根节点的值

它的左右子树也分别为二叉搜索树

1.2 操作-查找

如果根节点不为空：

如果根节点key == 查看key 返回true

如果根节点key > 查看key 在其左子树查找

如果根节点key < 查看key 在其右子树查找

否则返回false

实现代码：

class BinarySearchTree {public static class Node {int key;Node left;Node right;public Node(int key) {this.key = key;}}private Node root = null;/*** 搜索* @param key* @return*/public Node search(int key) {Node cur = root;while (cur != null){if(cur.key == key){return cur;}else if (key < cur.key){cur = cur.left;}else{cur = cur.right;}}return null;}
}

1.3 操作-新增

1.如果树为空树，即根 == null，直接插入

2.如果树不是空树，按照查找逻辑查找位置，插入新结点

实现代码：

class BinarySearchTree {public static class Node {int key;Node left;Node right;public Node(int key) {this.key = key;}}private Node root = null;/*** 插入** @param key* @return*/public boolean insert(int key) {Node cur = root;if (cur == null) {cur = new Node(key);return true;}Node parent = null;while (cur != null) {if (key == cur.key) {return false;} else if (key < cur.key) {parent = cur;cur = cur.left;} else {parent = cur;cur = cur.right;}}Node node = new Node(key);if (key < parent.key) {parent.right = node;} else {parent.left = node;}return true;}
}

1.4 操作-删除(难点)

设待删除结点为cur，待删除结点的双亲结点为parent

1.cur.left == null；

1. cur 是 root ，则 root = cur.right

2. cur 不是 root ， cur 是 parent.left ，则 parent.left = cur.right

3. cur 不是 root ， cur 是 parent.right ，则 parent.right = cur.right

2.cur.right == null；

1. cur 是 root ，则 root = cur.left

2. cur 不是 root ， cur 是 parent.left ，则 parent.left = cur.left

3. cur 不是 root ， cur 是 parent.right ，则 parent.right = cur.left

3.cur.left != null && cur.right != null；

需要使用替换法进行删除，即在它的右子树中寻找中序下的第一个结点(关键码最小)，用它的值填补到被删除节点中，再来处理该结点的删除问题。

实现代码：

class BinarySearchTree {public static class Node {int key;Node left;Node right;public Node(int key) {this.key = key;}}private Node root = null;/*** 删除** @param key* @return*/public boolean delete(int key) {Node cur = root;Node parent = null;while (cur != null) {if (key == cur.key) {deleteValue(cur, parent);return true;} else if (key < cur.key) {parent = cur;cur = cur.left;} else {parent = cur;cur = cur.right;}}return false;}public void deleteValue(Node cur, Node parent) {//cur左右孩子都不在if (cur.left == null && cur.right == null) {if (parent.right == cur) {parent.right = null;} else {parent.left = null;}//cur左孩子不在}else if (cur.left == null) {if (cur == root) {root = root.right;} else if (cur == parent.right) {parent.right = cur.right;} else {parent.left = cur.right;}//cur右孩子不在}else if (cur.right == null) {if (cur == root) {root = root.left;} else if (cur == parent.right) {parent.right = cur.left;} else {parent.left = cur.left;}//左右均在}else{//为删除节点的右节点Node target = cur.right;Node targetParent = cur;//找右树最左节点while (target.left != null){targetParent = target;target = target.left;}cur.key = target.key;if(targetParent.left == target){targetParent.left = target.right;}else{targetParent.right = target.right;}}}
}

1.5 总体实现代码

class BinarySearchTree {public static class Node {int key;Node left;Node right;public Node(int key) {this.key = key;}}private Node root = null;/*** 搜索** @param key* @return*/public Node search(int key) {Node cur = root;while (cur != null) {if (cur.key == key) {return cur;} else if (key < cur.key) {cur = cur.left;} else {cur = cur.right;}}return null;}/*** 插入** @param key* @return*/public boolean insert(int key) {Node cur = root;if (cur == null) {cur = new Node(key);return true;}Node parent = null;while (cur != null) {if (key == cur.key) {return false;} else if (key < cur.key) {parent = cur;cur = cur.left;} else {parent = cur;cur = cur.right;}}Node node = new Node(key);if (key < parent.key) {parent.right = node;} else {parent.left = node;}return true;}/*** 删除** @param key* @return*/public boolean delete(int key) {Node cur = root;Node parent = null;while (cur != null) {if (key == cur.key) {deleteValue(cur, parent);return true;} else if (key < cur.key) {parent = cur;cur = cur.left;} else {parent = cur;cur = cur.right;}}return false;}public void deleteValue(Node cur, Node parent) {//cur左右孩子都不在if (cur.left == null && cur.right == null) {if (parent.right == cur) {parent.right = null;} else {parent.left = null;}//cur左孩子不在}else if (cur.left == null) {if (cur == root) {root = root.right;} else if (cur == parent.right) {parent.right = cur.right;} else {parent.left = cur.right;}//cur右孩子不在}else if (cur.right == null) {if (cur == root) {root = root.left;} else if (cur == parent.right) {parent.right = cur.left;} else {parent.left = cur.left;}//左右均在}else{//为删除节点的右节点Node target = cur.right;Node targetParent = cur;//找右树最左节点while (target.left != null){targetParent = target;target = target.left;}cur.key = target.key;if(targetParent.left == target){targetParent.left = target.right;}else{targetParent.right = target.right;}}}
}

1.6 性能分析

      在二叉搜索树中，插入和删除操作都需要先进行查找。查找的效率直接影响了这些操作的性能。对于一个有n个节点的二叉搜索树，如果每个元素被查找的概率相等，那么平均查找长度将取决于节点在二叉搜索树中的深度。换句话说，节点越深，需要进行的比较次数就越多。

     然而，对于相同的关键码集合，如果插入关键码的顺序不同，可能会得到不同结构的二叉搜索树。这是因为二叉搜索树的性质要求左子树的所有节点的值小于根节点的值，右子树的所有节点的值大于根节点的值。因此，不同的插入顺序可能会导致树的结构有所不同，从而影响查找效率。

最优情况下，二叉搜索树为完全二叉树，其平均比较次数为：log(N）

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