二叉查找树和LISP的几种查找方式的比较.

Highflybird

我用LISP构建了一个二叉查找树，在对于数据已知的情况下，可以对每次查找获得很短的时间，效率很高。
二分搜索，又叫折半查找法：
是一种在有序数组中查找某一特定元素的搜索算法。搜素过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜素过程结束；如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空，则代表找不到。这种搜索算法每一次比较都使搜索范围缩小一半。
http://zh.wikipedia.org/wiki/%E6%8A%98%E5%8D%8A%E6%90%9C%E7%B4%A2%E7%AE%97%E6%B3%95
在很多情况下，对数据进行排序，然后采用二分查找法，或者构建二叉查找数，使得每一次的查找时间缩短为log(N)，达到最优效率。
我在这里给出了一个几个方法，说明如何构建二叉查找树，并实现折半搜索的。
主要代码：
二叉树的构建:
[pcode=lisp,true]
;;;=============================================================
;;;用AutoLISP构建一个二叉树(Construct a Binary Search tree)     
;;;从中间分开，直到分得只是剩下两个元素或者一个                 
;;;此结构用于查找一个元素，使得单次查找的时间为O(n) = log(n)   
;;;-------------------------------------------------------------
;;;输入: Lst 一个已经排序的表，可以拓展此表为点表或其他表。     
;;;输出: 一个二叉查找树                                         
;;;Author:Highflybird              in Shenzhen,China,2012-06-15
;;;=============================================================
(defun BTree (lst / L R)
  (cond                                                         
    ( (cddr lst)                                                ;the length of list > 2
      (setq R lst)
      (repeat (/ (length lst) 2)                                ;Split it
        (setq L (cons (car R) L))                               ;Left part of list
        (setq R (cdr R))                                        ;Right part of list
      )
      (cons (car R)                                             ;middle number as the first.
            (cons (BTree (reverse L))                           ;recurse Left part
                  (BTree (cdr R))                               ;recurse Right part
            )
      )
    )
    ( (cdr lst)                                                 ;just two elements
      (cons (cadr lst) (car lst))                               ;the right node is empty.
    )
    ( lst
      (car lst)                                                 ;if just one,the node is an element.
    )
  )
)
[/pcode]

以下是查找的实现方法：
[pcode=lisp,true]
;;;=============================================================
;;;用AutoLISP从二叉树中查找一个元素(Search a key in binary tree)
;;;每次查找总是从中间开始，如果不是，大于中间的就查找右边，小于
;;;中间则查找左边，直到原子或者点对表。                        
;;;因为树的最大深度不超过log(n)，故单次查找的时间为O(n)<=log(n)
;;;-------------------------------------------------------------
;;;输入: 要查找的Key，已经构建好的二叉查找树，n查询的最大节点数
;;;输出: 如果找到，返回找到的Key的位置。否则返回nil            
;;;Author:Highflybird              in Shenzhen,China,2012-06-15
;;;=============================================================
(defun BFind (key Tree n / L R i)
  (if (atom Tree)                                               ;if it's an atom,
    (if (= key Tree) 0)                                         ;set the index as 0
    (if (= (setq L (car Tree)) key)                             ;if left node = key
      (/ n 2)                                                   ;the index is the middle number.
      (if (atom (setq R (cdr Tree)))                            ;if the right node is an atom
        (if (= R key) 0)                                        ;and right node = key, set the index as 0
        (if (> L key)                                           ;if left node > key
          (BFind key (car R) (/ n 2))                           ;recurse Left
          (if (setq i (BFind key (cdr R) (/ (1- n) 2)))         ;otherwise recurse right
            (1+ (+ (/ n 2) i))                                  ;must add the index
          )
        )
      )
    )
  )
)
[/pcode]
另外，在附件里面，我给出了CAD的其他的几种查找方法：
遍历，vl-position, assoc,member等。
同时我附上了测试程序。希望此贴对大家有所帮助。

请点击此处下载

查看状态：需购买或无权限

您的用户组是：游客

文件名称:BinaryTree.LSP 
下载次数:89  文件大小:8.07 KB 
下载权限: 不限 以上  [免费赚D豆]

caozhengbai

抢到啦，哈哈

dnbcgrass

楼主知识渊博，胸怀宽大！

Lispboy

我帮大师解读下，什么是LISP二叉树。

1. 命令: (setq a '(1 2 3 4 5 6 7 8 9 10 11 12))
   
2. (1 2 3 4 5 6 7 8 9 10 11 12)
   
3. 命令: (btree a)
   
4. (7 (4 (2 1 . 3) 6 . 5) 10 (9 . 8) 12 . 11)
   

命令: (setq a '(1 2 3 4 5 6 7 8 9 10 11 12))<br /> (1 2 3 4 5 6 7 8 9 10 11 12)<br /> 命令: (btree a)<br /> (7 (4 (2 1 . 3) 6 . 5) 10 (9 . 8) 12 . 11)<br />

1、第一个元素是表中间元素
2、第二个元素是表头和中间元素中间元素递归，依次求中间构成的表3、每个表最后不能再分的情况下，是个点对。表示树叶子。除了树叶外的元素都是树枝。

pengfei2010

Lispboy 发表于 2013-6-9 23:10
我帮大师解读下，什么是LISP二叉树。

能说说什么时候能够用到吗？

zyhandw

还不懂什么是二叉树，下载来看看，感谢楼主的无私分享

QiaoCheng

给个图例

GTJ116600

基本是明白了，呵呵，看起来还是挺费劲的

rq28

大师这些漂亮代码都是来自独特解决方案的发现
闪烁着人类智慧的光芒

aeo

不明觉厉
BTree的时候不是已经罗列一遍了，应该已经找到，BFind就没必要了吧

除非数据结构就是 BTREE的状态。但这种状态怎么编程，lisp又没指针。

pengfei2010

要高深  整不明白啊

czx663

见过用C++构建的,见过用JAVA构建的，第一次看见Lisp构建的。第一眼看标题是想，没有指针的LISP，咋整二叉树啊。看完算是开了眼界了

守仁格竹GM

Lispboy 发表于 2013-6-9 23:10
我帮大师解读下，什么是LISP二叉树。

说白了就是 一半一半的找，省的挨个搜索，确实不错