一文搞懂 |
您所在的位置：网站首页 › 树搜索和图搜索图解人工智能 › 一文搞懂 |
一文搞懂
|
目录 1.搜索树的定义 2.插入操作 3.查找操作 4.删除操作 5.性能分析 6.完整代码 二叉搜索树又称为二叉排序树，它具有以下性质 1.若它的左子树不为空，则左子树上所有节点的值都小于根节点的值 2.若它的右子树不为空，则右子树上所有节点的值都大于根节点的值 3.它的左右子树也为二叉搜索树 以下就是一个二叉搜索树，每个节点的左节点小于父亲节的，右节点大于父亲节点。
首先判断根节点是否为空，为空直接添加，不为空的话就利用“每个节点的左节点小于父亲节的，右节点大于父亲节点”这个特点进行判断，并进行插入。 public boolean insert(int v){ if(root == null){ root = new Node(v); return true; } Node parent = null; Node cur = root; while(cur != null){ if(cur.val > v){ parent = cur; cur = cur.left; }else if (cur.val == v){ return false;//不能有相同的数据 }else { parent = cur; cur = cur.right; } } Node node = new Node(v); if(parent.val > v){ parent.left = node; }else if(parent.val < v){ parent.right = node; } return true; } 3.查找操作对于某个元素的查找，利用“每个节点的左节点小于父亲节的，右节点大于父亲节点”，进行判断，直至找到目标节点。 public Node Serach(int v){ Node cur = root; while(cur != null) { if (cur.val > v) { cur = cur.left; } else if (cur.val == v) { return cur; } else { cur = cur.right; } } return null; } 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 需要使用替换法 进行删除，即在它的右子树中寻找中序下的第一个结点 ( 关键码最小 ) ，用它的值填补到被删除节点中，再来处理该结点的删除问题。 public void remove(int v){ Node cur = root; Node parent = null; while(cur != null){ if(cur.val == v){ removeNode(cur,parent); break; }else if(cur.val > v){ parent = cur; cur = cur.left; }else { parent = cur; cur = cur.right; } } } public void removeNode(Node cur,Node parent){ if(cur.left == null){ if(cur == root){ root = cur.right; }else if(cur == parent.left){ parent.left = cur.right; }else{ parent.right = cur.right; } }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; } }else { Node targetParent = cur; Node target = cur.right; while(target.left != null){ targetParent = target; target = target.left; } cur.val = target.val; if(target == targetParent.left){ targetParent.left = target.right; }else { targetParent.right = target.right; } } } 5.性能分析 插入和删除操作都必须先查找，查找效率代表了二叉搜索树中各个操作的性能。 对有n个结点的二叉搜索树，若每个元素查找的概率相等，则二叉搜索树平均查找长度是结点在二叉搜索树的深度的函数，即结点越深，则比较次数越多。 最优情况：二叉搜索树为完全二叉树，其平均比较次数为 log(2)(N); 最差情况：二叉搜索树为单支树，其平均比较次数为 N/2。 6.完整代码 //节点定义 class Node{ public int val; public Node left; public Node right; public Node(int val){ this.val = val; } } public class BinarySearchTree { public Node root = null; //搜索操作 public Node Serach(int v){ Node cur = root; while(cur != null) { if (cur.val > v) { cur = cur.left; } else if (cur.val == v) { return cur; } else { cur = cur.right; } } return null; } //插入操作 public boolean insert(int v){ if(root == null){ root = new Node(v); return true; } Node parent = null; Node cur = root; while(cur != null){ if(cur.val > v){ parent = cur; cur = cur.left; }else if (cur.val == v){ return false;//不能有相同的数据 }else { parent = cur; cur = cur.right; } } Node node = new Node(v); if(parent.val > v){ parent.left = node; }else if(parent.val < v){ parent.right = node; } return true; } //删除操作 public void remove(int v){ Node cur = root; Node parent = null; while(cur != null){ if(cur.val == v){ removeNode(cur,parent); break; }else if(cur.val > v){ parent = cur; cur = cur.left; }else { parent = cur; cur = cur.right; } } } //删除操作的具体实现 public void removeNode(Node cur,Node parent){ if(cur.left == null){ if(cur == root){ root = cur.right; }else if(cur == parent.left){ parent.left = cur.right; }else{ parent.right = cur.right; } }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; } }else { Node targetParent = cur; Node target = cur.right; while(target.left != null){ targetParent = target; target = target.left; } cur.val = target.val; if(target == targetParent.left){ targetParent.left = target.right; }else { targetParent.right = target.right; } } } //中序遍历 public void inOrder(Node root){ if(root == null) return; inOrder(root.left); System.out.print(root.val+" "); inOrder(root.right); } } 测试用例： public static void main(String[] args) { int[] array = {10,8,19,3,9,4,7}; BinarySearchTree binarySearchTree = new BinarySearchTree(); for (int i = 0;i < array.length;i++){ binarySearchTree.insert(array[i]); } binarySearchTree.inOrder(binarySearchTree.root); System.out.println(); Node node = binarySearchTree.Serach(8); System.out.println(node.val); binarySearchTree.insert(15); binarySearchTree.inOrder(binarySearchTree.root); System.out.println(); binarySearchTree.remove(9); binarySearchTree.inOrder(binarySearchTree.root); }运行结果：
|
【本文地址】
今日新闻 |
推荐新闻 |