1.基本思想我们将学习一种能够将链表插入的灵活性和有序数组查找的高效性结合起来的符号表实现。具体来说,就是使用每个结点含有两个链接(链表中每个结点只含有一个链接)的二叉查找树来高效地实现符号表,这也是计算机科学中最重要的算法之一。定义:一棵二叉查找树(BST)是一棵二叉树,其中每 ...
1.基本思想
我们将学习一种能够将链表插入的灵活性和有序数组查找的高效性结合起来的符号表实现。具体来说,就是使用每个结点含有两个链接(链表中每个结点只含有一个链接)的二叉查找树来高效地实现符号表,这也是计算机科学中最重要的算法之一。
定义:一棵二叉查找树(BST)是一棵二叉树,其中每个结点都含有一个Comparable的键(以及相关联的值)且每个结点的键都大于其左子树中的任意结点的键而小于右子树的任意结点的键。
2.具体算法
/** * 算法3.3 基于二叉查找树的符号表 * Created by huazhou on 2015/12/1. */public class BST<Key extends Comparator<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){ //见续1 } public void put(Key key, Value val){ //见续1 }}
原标题:算法—8.二叉查找树
关键词:
*特别声明:以上内容来自于网络收集,著作权属原作者所有,如有侵权,请联系我们:
admin#shaoqun.com
(#换成@)。