基于二叉树的思路实现的“十叉树”

该数据结构用于以替代一些简单的本地缓存系统,并提供快速检索的功能。

业务场景:

用户帐号223,拥有下级帐号223001、223002、2230055、22312345...

用户帐号224,拥有下级帐号224002、2248888...

用户...

223和224,我们暂且叫他为大帐号,后面的都叫小帐号。

当这些小帐号发消息给系统时,需要识别出对应的大帐号,且小帐号的长度不等,不可以检索库表。

假设大帐号已经驻留在内存。

 

java:

/**
 * 基于二叉树的思路实现的“十叉树”,用于存储一些临时性的数据,并提供一些查询接口
 * @project xframework
 * @date 2013-1-11
 * @version 1.0
 * @author Jason5186@qq.com
 * 
 * @review_history
 * [2013-1-11] create by Jason
 */
public class BinaryTree {
	
	// 树的根结点
	private TreeNode root = null;
	
	/**
	 * 
	 */
	public BinaryTree() {
		// TODO Auto-generated constructor stub
		root = new TreeNode(0);
	}
	
	private class TreeNode {
		
		private int key; 
		private Object value;
		private TreeNode[] nodes = new TreeNode[10];
		
		
		public TreeNode(int key) {
			// TODO Auto-generated constructor stub
			this(key, null);
		}
		
		public TreeNode(int key, Object value) {
			this.key = key;
			this.value = value;
		}	
		
		
		public TreeNode setChildTreeNode(int key, Object value){
			
			synchronized(this){
				TreeNode treeNode = nodes[key];
				if (treeNode == null) {
					nodes[key] = new TreeNode(key);
				}
				getChildTreeNode(key).setValue(value);
			}
			
			return getChildTreeNode(key);
			
		}
		
		public TreeNode setChildTreeNode(int key){
			synchronized(this){
				TreeNode treeNode = nodes[key];
				if (treeNode == null) {
					nodes[key] = new TreeNode(key);
				}
			}
			
			return getChildTreeNode(key);
		}
		
		public TreeNode getChildTreeNode(int key){
			return nodes[key];
		}
		
		public int getKey() {
			return key;
		}
		
		public Object getValue(){
			return value;
		}
		
		public void removeValue(){
			this.value = null;
		}
		
		public void setValue(Object value){
			this.value = value;
		}
		
		public String toString()
		{
			
			return "(" + key + " , " + value + " )";
		}
		
	}
	
	/**
	 * 空返回 true ,否则返回 false . 
	 */
	public boolean isEmpty()
	{
		if (root == null) {
			return true;
		} else {
			return false;
		}			
	}
	
	
	public void TreeEmpty() throws Exception 
	{
		if (isEmpty()) {
			throw new Exception("树为空");
		}
	}
	
	
	
	/**
	 * 查找指定s_key对应的节点
	 * @param s_key
	 * @return TreeNode
	 * @throws Exception
	 */
	public TreeNode search(String s_key) throws Exception 
	{
		
		if (getRoot() == null) {
			throw new Exception("root node is null");
		}
		
		TreeNode treeNode = getRoot();
		
		char[] key_array = s_key.toCharArray();
		
		// 根据给定的s_key,遍历tree node的绝对路径,且以最短匹配的规则检索;
		// 命中后返回对应的tree node,否则返回Null。
		for (char skey : key_array) {
			
			int key = skey & 0xf;
			
			TreeNode t_treeNode = treeNode.getChildTreeNode(key);
			if (t_treeNode == null) {
				
				// 该节点尚未创建:
				return null;
			}else if (t_treeNode.getValue() != null) {
				
				// 命中:
				return t_treeNode;
			}else{
				
				// 否则,将遍历下一个节点:
				treeNode = t_treeNode;
			}
			
		}
		
		// 循环体之外,将视为未命中:
		return null;
		
	}
	
	
	/**
	 * 将指定的s_key放入节点,并设置对应的value
	 * @param s_key
	 * @param value
	 * @throws Exception 
	 */
	public void insert(String s_key, Object value) throws Exception{
		TreeNode treeNode = getRoot();
		
		char[] key_array = s_key.toCharArray();
		int s_key_length = key_array.length;
		int s_key_count = 1;
		/*
		 * 根据给定的key_array的长度,查找节点、布置节点并得到最后一个节点的tree node,然后赋值value。
		 */
		for (char skey : key_array) {
			
			int key = skey & 0xf;
			
			// 取某节点下,N个子节点中的一个分支:
			TreeNode t_treeNode = treeNode.getChildTreeNode(key);
			
			if (t_treeNode == null) {
				
				// 创建一个新的子节点:
				t_treeNode = treeNode.setChildTreeNode(key);
			}else{
				
				if (t_treeNode.getValue() != null && s_key_count != s_key_length) {
					
					treeNode = null;
					break;
				}
				
			}
			
			// 该节点已经存在,节点交换:
			treeNode = t_treeNode;
			
			s_key_count++;
		}
		
		if (treeNode != null) {
			
			// 为最后一个节点赋值:
			treeNode.setValue(value);
		}
		
		
	}
	
	
	/**
	 * 删除指定key的节点
	 * @param s_key
	 * @throws Exception
	 */
	public void delete(String s_key) throws Exception
	{
		TreeNode node = search(s_key);
		if (node == null) {
			throw new Exception("Tree node not found, Tree node key is:["+s_key+"]");
		}
		
		node.removeValue();
		node = null;
		
	}
	
	
	
	
	public TreeNode getRoot() {
		return root;
	}
	
	
}

Test:

public static void main(String[] args) 
    {
    	try {
	    	BinaryTree bt = new BinaryTree();

	    	String key = "223";
	    	String msg = "hello jason";
	    	bt.insert(key, msg);
	    	
	    	TreeNode node = bt.search(key);
	    	if (node != null) {
	    		System.out.println(node.getValue());
	    	}
	    	
	    	node = bt.search("223001");
	    	if (node != null) {
	    		System.out.println(node.getValue());
	    	}
	    	
	    	
	    	System.out.println("Done!");
	    	
    	} catch (Exception e) {
    		System.out.println(e.getMessage());
    		e.printStackTrace();
    	}
    }

 

 

 

.

此条目发表在technologys分类目录。将固定链接加入收藏夹。