二叉查找树 布满荆棘的人生 2022-07-16 00:22 228阅读 0赞 本文将会介绍一种能够将链表插入的灵活性和有序数组查找的高效性结合在一起的符号表实现。 **定义** 一颗二叉查找树(BST)是一颗二叉树,其中每个结点都含有一个Comparable的键(以及相关联的值)且每个结点的键都大于其左子树的任意结点的键而小于任意右结点的键。 其实现代码如下(采用泛型编写): public class BST<Key extends Comparable<Key>,Value>{ private Node root;//根节点 private class Node{ private Key key; private Value val; private Node left,right; private int N; public Node(Key key,Value val,int N){ this.key = key; this.val = val; this.N = N; }//构造方法 } //求二叉树大小 public int size(){ return size(root); } private int size(Node x){ if(x==null) return 0; else return x.N; } //二叉树查找 public Value get(Key key){ return get(root,key); } private Value get(Node x,Key key){ if(x==null) return null; int cmp = key.compareTo(x.key); if(cmp<0) return get(x.left,key); else if(cmp>0) return get(x.right,key); else return x.val; } //二叉树插入 public void put(Key key,Value val){ root = put(root,key,val); } private Node put(Node x,Key key,Value val){ if(x==null) return new Node(key,val,1); int cmp = key.compareTo(x.key); if(cmp < 0) x.left = put(x.left,key,val); else if(cmp > 0) x.right = put(x.right,key,val); else x.val = val;//键存在,则更新值 x.N = size(x.left) + size(x.right) + 1; return x; } //寻找最小键 public Key min(){ return min(root).key; } private Node min(Node x){ if(x==null) return x; return min(x.left); } //取整 public Key floor(Key key){ Node x = floor(root,key); if(x==null) return null; return x.key; } private Node floor(Node x,Key key){ if(x==null) return null; int cmp = key.compareTo(x.key); if(cmp==0) return x; if(cmp<0) return floor(x.left,key); Node t = floor(x.right,key); if(t!=null) return t; else return x; } //返回小于key值的键的数量 public int rank(Key key){ return rank(key,root); } private int rank(Key key,Node x){ if(x==null) return 0; int cmp = key.compareTo(x.key); if(cmp<0) return rank(key,x.left); else if(cmp>0) return 1+size(x.left)+rank(key,x.right); else return size(x.left); } //删除最小结点 public void deleteMin(){ root = deleteMin(root); } private Node deleteMin(Node x){ if(x.left==null) return x.right;//返回作为新的根节点 x.left = deleteMin(x.left);//递归删除,返回之后作为新的left子树 x.N = size(x.left)+size(x.right)+1; return x; } //删除操作,删除结点之后,使用右子树中的最小结点填补 public void delete(Key key){ root = delete(root,key); } public Node delete(Node x,Key key){ if(x==null) return null; int cmp = key.compareTo(x.key); if (cmp<0) x.left=delete(x.left,key);//调用递归 else if(cmp>0) x.right=delete(x.right,kry); else{ if(x.right==null) return x.left; if(x.left==null) return x.right; Node t =x; x = min(x.right);//使用右子树的最小结点代替 x.right = deteleMin(t.right); x.left = t.left; } x.N = size(x.left) + size(x.right) + 1; return x; } } 其中使用了很多递归,递归与非递归的区别是,递归的实现更容易验证其正确性,而非递归的实现效率更高。 二叉查找树的效率取决于树的高度,树的高度决定了算法在最坏情况下的性能,因此还可以对其进行优化为平衡二叉树,它能保证在无论键的插入顺序如何,树的高度都是总键数的对数。
相关 leetcode——二叉树、二叉查找树 leetcode——二叉树、二叉查找树 104. 二叉树的最大深度 111. 二叉树的最小深度 226. 翻转二叉树 r囧r小猫/ 2022年09月05日 12:39/ 0 赞/ 255 阅读
相关 二叉查找树 二叉查找树是二叉树中最常用的一种类型,也叫二叉搜索树。顾名思义,二叉查找树是为了实现快速查找而生的。不过,它不仅仅支持快速查找一个数据,还支持快速插入、删除一个数据。它是怎么做 港控/mmm°/ 2022年08月28日 03:51/ 0 赞/ 255 阅读
相关 二叉查找树 本文将会介绍一种能够将链表插入的灵活性和有序数组查找的高效性结合在一起的符号表实现。 定义 一颗二叉查找树(BST)是一颗二叉树,其中每个结点都含有一个Comparab 布满荆棘的人生/ 2022年07月16日 00:22/ 0 赞/ 229 阅读
相关 二叉查找树 package 树; /\\ \ 定义一个结点 \/ class Node\{ Node left = null; Node righ ╰+攻爆jí腚メ/ 2022年05月26日 07:49/ 0 赞/ 342 阅读
相关 二叉树(四)---查找二叉树 上次我说了如何去遍历一棵二叉树,今天我来说一说查找二叉树是怎样实现的。 首先我来介绍一下查找二叉树是怎样生成的。 这个是我为我的二叉树设置的一些基础的组成数据结构 深碍√TFBOYSˉ_/ 2022年05月25日 09:37/ 0 赞/ 277 阅读
相关 二叉查找树 <table> <tbody> <tr> <td> <p>package 树;</p> <p>import java.util.Stack;</p> <p>/ 我就是我/ 2022年05月13日 01:40/ 0 赞/ 277 阅读
相关 二叉查找树 二叉查找树 概念 二叉查找树,又称为二叉排序树、二叉搜索树。 二叉查找树有以下几个特性 若左子树不空,则左子树上所有结点的值均小于它的根结点的值 若 旧城等待,/ 2022年04月10日 02:39/ 0 赞/ 489 阅读
相关 二叉查找树 / 这是一个二叉查找树,实现了以下操作:插入结点、构造二叉树、删除结点、查找、 查找最大值、查找最小值、查找指定结点的前驱和后继。上述所有操作时 迈不过友情╰/ 2022年02月26日 11:48/ 0 赞/ 344 阅读
相关 二叉查找树 二叉查找树有这几个规则 1、若左子树不为空,那么左子树所有节点的值小于均小于他的根节点的值。 2、若右子树不为空,那么右子树的所有节点的值大于根节点的值。 3、左右子树也 ﹏ヽ暗。殇╰゛Y/ 2021年09月22日 09:40/ 0 赞/ 543 阅读
相关 二叉查找树 理解 在二叉树的基础上,假设一个节点值都为Integer类型,现在有一个节点A,那么A的左子树中的所有值一定小于A节点的值,A的右子树中的所有值一定大于A的节点的值,如果 清疚/ 2021年09月11日 06:56/ 0 赞/ 542 阅读
还没有评论,来说两句吧...