Topic: binary tree

[Jeremy Dunn]

Looking for some help here. Here is what I want to do, I wish to have a function that we will call BTREE (for binary tree). The function takes a list of integers (or whatever) that has a length of a power of 2 (2, 4, 8 etc) and repeatedly divides the list in half creating a binary tree of conses. An example would be

(btree '(a b c d e f g h))  -> (((a . b) . (c . d)) . ((e . f) .(g . h)))

Let the programs begin!

[gile]

Hi,

It seems to me your request is not possible.

The item following a dot have to be an atom:
- dotted pair: (a . b) where b is an atom.
- dotted list: (a b c . d) where d is an atom

Code - Auto/Visual Lisp: [Select]

1. '(((1 . 2) . (3 . 4)) . ((5 . 6) . (7 . 8)))

is a shortcut for :

Code - Auto/Visual Lisp: [Select]

1. (cons (cons (cons 1 2) (cons 3 4)) (cons (cons 5 6) (cons 7 8)))

which is evaluated to:

Code - Auto/Visual Lisp: [Select]

1. (((1 . 2) 3 . 4) (5 . 6) 7 . 8)

[Grrr1337]

initial attempt:

Code - Auto/Visual Lisp: [Select]

1. (defun foo ( L / f )
2.   (defun f ( L )
3.     (if L
4.       (cons
5.         ('((a b) ((if (vl-every 'atom (list a b)) cons list) a b))
6.           (car L)
7.           (cadr L)
8.         )
9.         (f (cddr L))
10.       )
11.     )
12.    
13.   )
14.   (cond
15.     ( (vl-consp L)
16.       (setq L (f L))
17.       (while (and L (zerop (rem (length (setq L (f L))) 2))))
18.       L
19.     )
20.   )
21. )

Code - Auto/Visual Lisp: [Select]

1. _$ (foo '(a b c d e f g))
2. ((((A . B) (C . D)) ((E . F) (G))))
3. _$ (foo '(a b c d e f g h))
4. ((((A . B) (C . D)) ((E . F) (G . H))))
5. _$ (foo '(a b c d e f g h i j k l m n o p q))
6. (((A . B) (C . D)) ((E . F) (G . H)) ((I . J) (K . L)) ((M . N) (O . P)) ((Q) nil))
7. _$ (foo '(a b c d e f g h i j k l m n o p q r))
8. (((A . B) (C . D)) ((E . F) (G . H)) ((I . J) (K . L)) ((M . N) (O . P)) ((Q . R) nil))
9. _$ (foo '(a b c d e f g h i j k l m n o p q r s t))
10. (((A . B) (C . D)) ((E . F) (G . H)) ((I . J) (K . L)) ((M . N) (O . P)) ((Q . R) (S . T)))
11. _$ (foo '(a b c d e f g h i j k l m n o p q r s t u v w x y z))
12. (((A . B) (C . D)) ((E . F) (G . H)) ((I . J) (K . L)) ((M . N) (O . P)) ((Q . R) (S . T)) ((U . V) (W . X)) ((Y . Z) nil))
13. _$ (foo '(a b c d e f g h i j k l m n o p q r s t u v w x y z 1 2 3 4))
14. ((((((A . B) (C . D)) ((E . F) (G . H))) (((I . J) (K . L)) ((M . N) (O . P)))) ((((Q . R) (S . T)) ((U . V) (W . X))) (((Y . Z) (1 . 2)) ((3 . 4) nil)))))
15. _$ (foo '(1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30))
16. ((((((1 . 2) (3 . 4)) ((5 . 6) (7 . 8))) (((9 . 10) (11 . 12)) ((13 . 14) (15 . 16)))) ((((17 . 18) (19 . 20)) ((21 . 22) (23 . 24))) (((25 . 26) (27 . 28)) ((29 . 30) nil)))))
17.  

[gile]

Typically a LISP tree structure is a lis of sublists.

(1 2 3 4 5 6 7 8 ) => (((1 2) (3 4)) ((5 6) (7 8 )))

Code - Auto/Visual Lisp: [Select]

1. (defun btree (l / foo bar n)
2.  
3.   (defun foo (l / n)
4.     (if (< (setq n (/ (length l) 2)) 2)
5.       l
6.       (mapcar 'foo (bar n l nil))
7.     )
8.   )
9.  
10.   (defun bar (n l a)
11.     (if (zerop n)
12.       (list (reverse a) l)
13.       (bar (1- n) (cdr l) (cons (car l) a))
14.     )
15.   )
16.  
17.   ((lambda (n)
18.      (if (= (fix n) n)
19.        (foo l)
20.      )
21.    )
22.     (/ (log (length l)) (log 2))
23.   )
24. )

[David Bethel]

It seems to me your request is not possible.

I agree with Gile

Dotted pair lists must always contain two members and is the method AutoLISP uses to maintain entity definition data.

When representing a dotted pair, members of the list are separated by a period ( . ). Most list-handling functions do not accept a dotted pair as an argument, so you should be sure you are passing the right kind of list to a function.

https://knowledge.autodesk.com/search-result/caas/CloudHelp/cloudhelp/2016/ENU/AutoCAD-AutoLISP/files/GUID-877B87BA-6FA2-4894-9F94-184E7DF25B7D-htm.html

-David

[JohnK]

gile is correct; in lisp a tree is a list of lists.

Here is some binary tree lisp code (copied from some notes of mine).

Code - Auto/Visual Lisp: [Select]

1. ;;
2. ;; Binary Trees
3. ;;
4. (defun let (bindings body)
5.       ;; let for autolisp.
6.       ;;
7.       ;; Ex:
8.       ;; (let '((x 10) (y 20))                         ; bindings
9.       ;;      '((princ "\nLocal values of X and Y: ")  ; body
10.       ;;        (prin1 x)
11.       ;;        (prin1 y)
12.       ;;        (princ)
13.       ;;     )
14.       ;;   )
15.       ;;
16.       (eval
17.         (cons (append (list 'lambda (mapcar 'car bindings)) body)
18.               (mapcar 'cadr bindings))) )
19.  
20. ;;
21. ;; Constructors for binary trees
22. ;;
23. (defun make-bin-tree-leaf (E)
24. ;;;  "Create a leaf."
25.   (list E))
26.  
27. (defun make-bin-tree-node (E B1 B2)
28. ;;;  "Create a node with element K, left subtree B1 and right subtree B2."
29.   (list E B1 B2))
30.  
31. ;;
32. ;; Selectors for binary trees
33. ;;
34. (defun bin-tree-leaf-element (L)
35. ;;;  "Retrieve the element of a leaf L."
36.   (car L))
37.  
38. (defun bin-tree-node-element (N)
39. ;;;  "Retrieve the element of a node N."
40.   (car N))
41.  
42. (defun bin-tree-node-left (N)
43. ;;;  "Retrieve the left subtree of a node N."
44.   (cadr N))
45.  
46. (defun bin-tree-node-right (N)
47. ;;;  "Retrieve the right subtree of a node N."
48.   (caddr N))
49.  
50. ;;
51. ;; Recognizers for binary trees
52. ;;
53. (defun bin-tree-leaf-p (B)
54. ;;;  "Test if binary tree B is a leaf."
55.   (and (listp B) (= (length B) 1)))
56.  
57. (defun bin-tree-node-p (B)
58. ;;;  "Test if binary tree B is a node."
59.   (and (listp B) (= (length B) 3)))
60.  
61. (defun bin-tree-member-p (B E)
62. ;;;  "Test if E is an element in binary tree B."
63.   (if (bin-tree-leaf-p B)
64.       (equal E (bin-tree-leaf-element B))
65.     (or (equal E (bin-tree-node-element B))
66.         (bin-tree-member-p (bin-tree-node-left B) E)
67.         (bin-tree-member-p (bin-tree-node-right B) E))))
68.  
69.  
70. ;;
71. ;; Construction of a binary tree
72. ;;
73. (setq my-bin-tree
74.        (make-bin-tree-node '*
75.          (make-bin-tree-node '+
76.            (make-bin-tree-leaf 2)
77.            (make-bin-tree-leaf 3)
78.          )
79.          (make-bin-tree-node '-
80.            (make-bin-tree-leaf 7)
81.            (make-bin-tree-leaf 8)
82.          )
83.        )
84. )
85. ;; --> (* (+ (2) (3)) (- (7) (8)))
86. ;;
87. ;;            *
88. ;;           / \
89. ;;          /   \
90. ;;         /     \
91. ;;        +       -
92. ;;       / \     / \
93. ;;      2   3   7   8
94.  
95. ;;;(trace bin-tree-member-p)
96. (bin-tree-member-p my-bin-tree 7)
97. (bin-tree-member-p my-bin-tree 8)
98. (bin-tree-member-p my-bin-tree 9)
99.  

However, binary trees come in several different flavors. For example, if you need to parse something and preform a lot of searching on the data you'd use a Binary Search Tree. Since Binary trees are essentially just lists and reordering lists (especially large ones) can be very memory expensive in Lisp you typically design your procedures to gobble up lists efficiently and quickly instead of recreating lists again and again.

[Stefan]

...The function takes a list of integers (or whatever) that has a length of a power of 2 (2, 4, 8 etc) ...

My version, creating list of lists, for exactly 2^n items

Code - Auto/Visual Lisp: [Select]

1. (defun btree (l / a r)
2.   (foreach b l
3.     (if a
4.       (setq r (cons (list a b) r) a nil)
5.       (setq a b)
6.     )
7.   )
8.   (if (cddr r) (btree (reverse r)) (reverse r))
9. )

[Jeremy Dunn]

Stefan's function works just fine for what I am trying to do. I guess my question now is how does a dotted pair differ from a list and when do you use one over the other?

[gile]

Stefan's function works just fine for what I am trying to do. I guess my question now is how does a dotted pair differ from a list and when do you use one over the other?

One primary record structure in LISP is the 'cons cell' which contains two pointers: the CAR (Contents of the Address Register) and the CDR (Contents of the Decrement Register).

A cons cell is built using the CONS function.

If both car and cdr point to an atom, the result is a dotted pair:
(cons 1 2) => (1 . 2)
(car '(1 . 2)) => 1
(cdr '(1 . 2)) => 2

A LISP list (singly linked list) is recursively defined to be either the empty list (nil) or a cons cell whose cdr points to a list
(cons 1 (2)) => (1 2)
(car '(1 2)) => 1
(cdr '(1 2)) => (2)

(list 1 2 3 4) is a shortcut for (cons 1 (cons 2 (cons 3 (cons 4 nil))))

[Grrr1337]

I thought that DXF assoc list (or list of dotted pairs) resemble the hashtable from C#,
since they both deal with dictionaries and their items have key and value properties.
Anyway I can't delve more than this (because I'm a C# newbie).

BTW agree with gile, about the list structure - I use dotted pairs only when I'm forced to.. like within ssget/modifying elists via entget+subst+entmod/etc..

[ribarm]

...The function takes a list of integers (or whatever) that has a length of a power of 2 (2, 4, 8 etc) ...

My version, creating list of lists, for exactly 2^n items

Code - Auto/Visual Lisp: [Select]

1. (defun btree (l / a r)
2.   (foreach b l
3.     (if a
4.       (setq r (cons (list a b) r) a nil)
5.       (setq a b)
6.     )
7.   )
8.   (if (cddr r) (btree (reverse r)) (reverse r))
9. )

This last line eludes me :

Code: [Select]

...
  (if (cddr r) (btree (reverse r)) (reverse r))
...
I thought if you need one big list one (cdr r) would be enough...

[ribarm]

OK... I figured out : final list should have 2 big sublists, thus (cddr r)...

[EDIT : And not only final list, but all recursion processed sublists should have at least 2 elements (lists or atoms) and therefore (cddr r) was written in order to make recursion works correctly at each processing step...]

[gile]

I thought that DXF assoc list (or list of dotted pairs) resemble the hashtable from C#,
since they both deal with dictionaries and their items have key and value properties.
Anyway I can't delve more than this (because I'm a C# newbie).

If the use association list and the assoc function looks like getting values by keys in a dictionary structure, the linked list (the only data stucture used in AutoLISP) is not at all the same thing as a dictionary data structure.
A dictionary does not allow duplicated keys, an association list may have multiple entries with the same 'key' (DXF code 10, 40, 41, 42 for LWPOLYTLINE vertices).
If a linked list is cheap to access from left to end, it's far less efficient than a dictionary for random access lookup by 'key' because the list must be traversed from the left at each lookup (i.e. O(n) access time where n is the length of the list), on the other hand, the dictionary is based on a Hashtable which allows a direct random access lookup by key (i.e. O(1) time access).

[gile]

A sort function using a binary tree here.

[Lee Mac]

Essentially the opposite of Stefan's:

Code - Auto/Visual Lisp: [Select]

1. (defun btree ( l / r )
2.     (if (cddr l)
3.         (progn
4.             (repeat (/ (length l) 2)
5.                 (setq r (cons (car l) r) l (cdr l))
6.             )
7.             (list (btree (reverse r)) (btree l))
8.         )
9.         l
10.     )
11. )