成都网站建设新闻,wordpress网站投放广告,泰安网络公司平台,延吉市住房城乡建设局网站系列文章#xff1a; 1. 先导片--MapSet之二叉搜索树 2. MapSet之相关概念
目录
前言
1.二叉搜索树
1.1 定义
1.2 操作-查找
1.3 操作-新增
1.4 操作-删除(难点)
1.5 总体实现代码
1.6 性能分析 前言 TreeMap 和 TreeSet 是 Java 中基于搜索树实现的 M…系列文章 1. 先导片--MapSet之二叉搜索树 2. MapSet之相关概念
目录
前言
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
