MapSet之二叉搜索树

系列文章：

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

                 2.   Map&Set之相关概念

目录

前言

1.二叉搜索树

1.1 定义

1.2 操作-查找

1.3 操作-新增

1.4 操作-删除(难点)

1.5 总体实现代码

1.6 性能分析

前言

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 性能分析