Binary search tree (Scheme)
From LiteratePrograms
- Other implementations: C | C++ | Haskell | Java | Scheme | Standard ML
Binary Trees
Suppose we want to create a new kind of recursive data type, our familiar binary trees. The first thing we have to do is to define the data type in terms of its constructors, selectors and recognizers. In the case of binary trees, we have the following:
Constructors: We have two kinds of binary trees, leaves and nodes. Accordingly, we need a constructor for each kind: (make-bin-tree-leaf E): A leaf is a composite object with one component, the element E. (make-bin-tree-node E B1 B2): A node consists of three components, an element E, a left subtree B1 and a right subtree B2. Each of B1 and B2 is a binary tree. Notice that the definition of binary tree is inherently recursive (as in the case of nodes). Larger binary trees can be composed from smaller ones. Selectors: We need to define a selector for each component of each kind of binary tree. (bin-tree-leaf-element L): Retrieve the element of a leaf L. (bin-tree-node-element N): Retrieve the element of a node N. (bin-tree-node-left N): Retrieve the left subtree of a node N. (bin-tree-node-right N): Retrieve the right subtree of a node N. Recognizers: We define one recognizer for each kind of binary tree. (bin-tree-leaf-p B): Test if a given binary tree B is a leaf. (bin-tree-node-p B): Test if a given binary tree B is a node. Notice that we have not written a line of code yet, and still we are able to write down the function signature of all the constructors, selectors and recognizers. The process is more or less mechanical:
Define a constructor for each variant of the recursive data type. The parameters for a constructor defines the components of a composite object. For each parameter of each constructor, define a selector to retrieve the corresponding component. For each constructor, define a corresponding recognizer. The next question is how we are to represent a binary tree as a LISP object. Of course, a list is the first thing that comes to our mind:
We represent an leaf with element E by a singleton list containing E (i.e. (list E)). A node with element E, left subtree B1 and right subtree B2 is represented as a list containing the three components (i.e. (list E B1 B2)). Fixing the representation, we can thus implement the recursive data type functions:
;;
;; Binary Trees
;;
;;
;; Constructors for binary trees
;;
(defun make-bin-tree-leaf (E)
"Create a leaf."
(list E))
(defun make-bin-tree-node (E B1 B2)
"Create a node with element K, left subtree B1 and right subtree B2."
(list E B1 B2))
;;
;; Selectors for binary trees
;;
(defun bin-tree-leaf-element (L)
"Retrieve the element of a leaf L."
(first L))
(defun bin-tree-node-element (N)
"Retrieve the element of a node N."
(first N))
(defun bin-tree-node-left (N)
"Retrieve the left subtree of a node N."
(second N))
(defun bin-tree-node-right (N)
"Retrieve the right subtree of a node N."
(third N))
;;
;; Recognizers for binary trees
;;
(defun bin-tree-leaf-p (B)
"Test if binary tree B is a leaf."
(and (listp B) (= (list-length B) 1)))
(defun bin-tree-node-p (B)
"Test if binary tree B is a node."
(and (listp B) (= (list-length B) 3)))
The representation scheme works out like the following:
USER(5): (make-bin-tree-node '*
(make-bin-tree-node '+
(make-bin-tree-leaf 2)
(make-bin-tree-leaf 3))
(make-bin-tree-node '-
(make-bin-tree-leaf 7)
(make-bin-tree-leaf 8)))
(* (+ (2) (3)) (- (7) (8))) The expression above is a binary tree node with element * and two subtrees. The left subtree is itself a binary tree node with + as its element and leaves as its subtress. The right subtree is also a binary tree node with - as its element and leaves as its subtrees. All the leaves are decorated by numeric components.
*
/ \
/ \
/ \
+ -
/ \ / \
2 3 7 8
Searching Binary Trees
As discussed in previous tutorials, having recursive data structures defined in the way we did streamlines the process of formulating structural recursions. We review this concept in the following examples.
Suppose we treat binary trees as containers. An expression E is a member of a binary tree B if:
B is a leaf and its element is E. B is a node and either its element is E or E is a member of one of its subtrees. For example, the definition asserts that the members of (* (+ (2) (3)) (- (7) (8))) are *, +, 2, 3, -, 7 and 8. Such a definition can be directly implemented by our recursive data type functions:
(defun bin-tree-member-p (B E)
"Test if E is an element in binary tree B."
(if (bin-tree-leaf-p B)
(equal E (bin-tree-leaf-element B))
(or (equal E (bin-tree-node-element B))
(bin-tree-member-p (bin-tree-node-left B) E)
(bin-tree-member-p (bin-tree-node-right B) E))))
The function can be made more readable by using the let form:
(defun bin-tree-member-p (B E)
"Test if E is an element in binary tree B."
(if (bin-tree-leaf-p B)
(equal E (bin-tree-leaf-element B))
(let
((elmt (bin-tree-node-element B))
(left (bin-tree-node-left B))
(right (bin-tree-node-right B)))
(or (equal E elmt)
(bin-tree-member-p left E)
(bin-tree-member-p right E)))))
Tracing the execution of bin-tree-member-p, we get:
USER(14): (trace bin-tree-member-p) (BIN-TREE-MEMBER-P) USER(15): (bin-tree-member-p '(+ (* (2) (3)) (- (7) (8))) 7)
0: (BIN-TREE-MEMBER-P (+ (* (2) (3)) (- (7) (8))) 7)
1: (BIN-TREE-MEMBER-P (* (2) (3)) 7)
2: (BIN-TREE-MEMBER-P (2) 7)
2: returned NIL
2: (BIN-TREE-MEMBER-P (3) 7)
2: returned NIL
1: returned NIL
1: (BIN-TREE-MEMBER-P (- (7) (8)) 7)
2: (BIN-TREE-MEMBER-P (7) 7)
2: returned T
1: returned T
0: returned T
T Exercise: Let size(B) be the number of members in a binary tree B. Give a recursive definition of size(B), and then implement a LISP function (bin-tree-size B) that returns size(B). Traversing Binary Trees
Let us write a function that will reverse a tree in the sense that the left and right subtrees of every node are swapped:
(defun binary-tree-reverse (B)
"Reverse binary tree B."
(if (bin-tree-leaf-p B)
B
(let
((elmt (bin-tree-node-element B))
(left (bin-tree-node-left B))
(right (bin-tree-node-right B)))
(make-bin-tree-node elmt
(binary-tree-reverse right)
(binary-tree-reverse left)))))
The correctness of the above implementation can be articulated as follows. Given a binary tree B and an object E, either the binary tree is a leaf or it is a node: We have to approach each case differently.
Case 1: B is a leaf. Then the reversal of B is simply B itself. Case 2: B is a node. Then B has three components, namely, an element elmt, a left subtree left and a right subtree right. The reversal of B is a node with element elmt, left subtree the reversal of right, and right subtree the reversal of left. The following shows us how the recursion unfolds:
USER(21): (trace bin-tree-reverse) (BIN-TREE-REVERSE) USER(22): (bin-tree-reverse '(* (+ (2) (3)) (- (7) (8))))
0: (BIN-TREE-REVERSE (* (+ (2) (3)) (- (7) (8))))
1: (BIN-TREE-REVERSE (- (7) (8)))
2: (BIN-TREE-REVERSE (8))
2: returned (8)
2: (BIN-TREE-REVERSE (7))
2: returned (7)
1: returned (- (8) (7))
1: (BIN-TREE-REVERSE (+ (2) (3)))
2: (BIN-TREE-REVERSE (3))
2: returned (3)
2: (BIN-TREE-REVERSE (2))
2: returned (2)
1: returned (+ (3) (2))
0: returned (* (- (8) (7)) (+ (3) (2)))
(* (- (8) (7)) (+ (3) (2))) The resulting expression represents the following tree:
*
/ \
/ \
/ \
- +
/ \ / \
8 7 3 2
Let us implement a function that will extract the members of a given binary tree, and put them into a list in preorder.
(defun bin-tree-preorder (B)
"Create a list containing keys of B in preorder."
(if (bin-tree-leaf-p B)
(list (bin-tree-leaf-element B))
(let
((elmt (bin-tree-node-element B))
(left (bin-tree-node-left B))
(right (bin-tree-node-right B)))
(cons elmt
(append (bin-tree-preorder left)
(bin-tree-preorder right))))))
Tracing the execution of the function, we obtain the following: USER(13): (trace bin-tree-preorder) (BIN-TREE-PREORDER) USER(14): (bin-tree-preorder '(* (+ (2) (3)) (- (7) (8))))
0: (BIN-TREE-PREORDER (* (+ (2) (3)) (- (7) (8))))
1: (BIN-TREE-PREORDER (+ (2) (3)))
2: (BIN-TREE-PREORDER (2))
2: returned (2)
2: (BIN-TREE-PREORDER (3))
2: returned (3)
1: returned (+ 2 3)
1: (BIN-TREE-PREORDER (- (7) (8)))
2: (BIN-TREE-PREORDER (7))
2: returned (7)
2: (BIN-TREE-PREORDER (8))
2: returned (8)
1: returned (- 7 8)
0: returned (* + 2 3 - 7 8)
(* + 2 3 - 7 8) As we have discussed before, the append call in the code above is a source of inefficiency that can be obtimized away:
(defun fast-bin-tree-preorder (B)
"A tail-recursive version of bin-tree-preorder."
(preorder-aux B nil))
(defun preorder-aux (B A)
"Append A to the end of the list containing elements of B in preorder."
(if (bin-tree-leaf-p B)
(cons (bin-tree-leaf-element B) A)
(let
((elmt (bin-tree-node-element B))
(left (bin-tree-node-left B))
(right (bin-tree-node-right B)))
(cons elmt
(preorder-aux left
(preorder-aux right A))))))
An execution trace of the implementation is the following: USER(15): (trace fast-bin-tree-preorder preorder-aux) (PREORDER-AUX FAST-BIN-TREE-PREORDER) USER(16): (fast-bin-tree-preorder '(* (+ (2) (3)) (- (7) (8))))
0: (FAST-BIN-TREE-PREORDER (* (+ (2) (3)) (- (7) (8))))
1: (PREORDER-AUX (* (+ (2) (3)) (- (7) (8))) NIL)
2: (PREORDER-AUX (- (7) (8)) NIL)
3: (PREORDER-AUX (8) NIL)
3: returned (8)
3: (PREORDER-AUX (7) (8))
3: returned (7 8)
2: returned (- 7 8)
2: (PREORDER-AUX (+ (2) (3)) (- 7 8))
3: (PREORDER-AUX (3) (- 7 8))
3: returned (3 - 7 8)
3: (PREORDER-AUX (2) (3 - 7 8))
3: returned (2 3 - 7 8)
2: returned (+ 2 3 - 7 8)
1: returned (* + 2 3 - 7 8)
0: returned (* + 2 3 - 7 8)
(* + 2 3 - 7 8) Exercise: Implement a function that will create a list containing members of a given binary tree in postorder. Implement also a tail-recursive version of the same function.
Exercise: Repeat the last exercise with inorder.
Abstract Data Types
Abstract data types are blackboxes. They are defined in terms of their external interfaces, and not their implementation. For example, a set abstraction offers the following operations:
(make-empty-set) creates an empty set. (set-insert S E) returns a set containing all members of set S plus an additional member E. (set-remove S E) returns a set containing all members of set S except for E. (set-member-p S E) returns true if E is a member of set S. (set-empty-p S) returns true if set S is empty. To implement an abstract data type, we need to decide on a representation. Let us represent a set by a list with no repeated members.
(defun make-empty-set () "Creates an empty set." nil) (defun set-insert (S E) "Return a set containing all the members of set S plus the element E." (adjoin E S :test #'equal)) (defun set-remove (S E) "Return a set containing all the members of set S except for element E." (remove E S :test #'equal)) (defun set-member-p (S E) "Return non-NIL if set S contains element E." (member E S :test #'equal)) (defun set-empty-p (S) "Return true if set S is empty." (null S))
Exercise: Look up the definition of adjoin, remove and member from CLTL2. In particular, find out how the :test keyword is used to specify the equality test function to be used by the three functions. What will happen if we omit the :test keyword and the subsequent #'equal when invoking the three functions? Notice that we have implemented an abstract data type (sets) using a more fundamental recursive data structure (lists) with additional computational constraints (no repetition) imposed by the interface functions.
Binary Search Trees
Another way of implementing the same set abstraction is to use the more efficient binary search tree (BST). Binary search trees are basically binary trees with the following additional computational constraints:
All the members in the left subtree of a tree node is no greater than the element of the node. All the members in the right subtree of a tree node is greater than the element of the node. All the leaf members are distinct. Again, we are implementing an abstract data type (sets) by a more fundamental recursive data structure (binary trees) with additional computational constraints. In particular, we use the leaves of a binary tree to store the member of a set, and the tree nodes for providing indexing information that improves search performance. for example, a BST representing the set {1 2 3 4} would look like:
2
/ \
/ \
/ \
1 3
/ \ / \
1 2 3 4
An empty BST is represented by NIL, while a nonempty BST is represented by a binary tree. We begin with the constructor and recognizer for empty BST.
(defun make-empty-BST ()
"Create an empty BST."
nil)
(defun BST-empty-p (B)
"Check if BST B is empty."
(null B))
Given the additional computational constraints, membership test can be implemented as follows:
(defun BST-member-p (B E)
"Check if E is a member of BST B."
(if (BST-empty-p B)
nil
(BST-nonempty-member-p B E)))
(defun BST-nonempty-member-p (B E)
"Check if E is a member of nonempty BST B."
(if (bin-tree-leaf-p B)
(= E (bin-tree-leaf-element B))
(if (<= E (bin-tree-node-element B))
(BST-nonempty-member-p (bin-tree-node-left B) E)
(BST-nonempty-member-p (bin-tree-node-right B) E))))
Notice that we handle the degenerate case of searching an empty BST separately, and apply the well-known recursive search algorithm only on nonempty BST. USER(16): (trace BST-member-p BST-nonempty-member-p) (BST-NONEMPTY-MEMBER-P BST-MEMBER-P) USER(17): (BST-member-p '(2 (1 (1) (2)) (3 (3) (4))) 3)
0: (BST-MEMBER-P (2 (1 (1) (2)) (3 (3) (4))) 3)
1: (BST-NONEMPTY-MEMBER-P (2 (1 (1) (2)) (3 (3) (4))) 3)
2: (BST-NONEMPTY-MEMBER-P (3 (3) (4)) 3)
3: (BST-NONEMPTY-MEMBER-P (3) 3)
3: returned T
2: returned T
1: returned T
0: returned T
T Insertion is handled by the following family of functions:
(defun BST-insert (B E)
"Insert E into BST B."
(if (BST-empty-p B)
(make-bin-tree-leaf E)
(BST-nonempty-insert B E)))
(defun BST-nonempty-insert (B E)
"Insert E into nonempty BST B."
(if (bin-tree-leaf-p B)
(BST-leaf-insert B E)
(let ((elmt (bin-tree-node-element B))
(left (bin-tree-node-left B))
(right (bin-tree-node-right B)))
(if (<= E (bin-tree-node-element B))
(make-bin-tree-node elmt
(BST-nonempty-insert (bin-tree-node-left B) E)
right)
(make-bin-tree-node elmt
left
(BST-nonempty-insert (bin-tree-node-right B) E))))))
(defun BST-leaf-insert (L E)
"Insert element E to a BST with only one leaf."
(let ((elmt (bin-tree-leaf-element L)))
(if (= E elmt)
L
(if (< E elmt)
(make-bin-tree-node E
(make-bin-tree-leaf E)
(make-bin-tree-leaf elmt))
(make-bin-tree-node elmt
(make-bin-tree-leaf elmt)
(make-bin-tree-leaf E))))))
As before, recursive insertion to nonempty BST is handled outside of the general entry point of BST insertion. Traversing down the index nodes, the recursive algorithm eventually arrives at a leaf. In case the element is not already in the tree, the leaf is turned into a node with leaf subtrees holding the inserted element and the element of the original leaf. For example, if we insert 2.5 into the tree represented by (2 (1 (1) (2)) (3 (3) (4))), the effect is the following:
2 2
/ \ / \
/ \ / \
/ \ ==> / \
1 3 1 3
/ \ / \ / \ / \
1 2 3 4 1 2 2.5 4
/ \
2.5 3
A trace of the insertion operation is given below: USER(22): (trace BST-insert BST-nonempty-insert BST-leaf-insert) (BST-LEAF-INSERT BST-NONEMPTY-INSERT BST-INSERT) USER(23): (BST-insert '(2 (1 (1) (2)) (3 (3) (4))) 2.5)
0: (BST-INSERT (2 (1 (1) (2)) (3 (3) (4))) 2.5)
1: (BST-NONEMPTY-INSERT (2 (1 (1) (2)) (3 (3) (4))) 2.5)
2: (BST-NONEMPTY-INSERT (3 (3) (4)) 2.5)
3: (BST-NONEMPTY-INSERT (3) 2.5)
4: (BST-LEAF-INSERT (3) 2.5)
4: returned (2.5 (2.5) (3))
3: returned (2.5 (2.5) (3))
2: returned (3 (2.5 (2.5) (3)) (4))
1: returned (2 (1 (1) (2)) (3 (2.5 (2.5) (3)) (4)))
0: returned (2 (1 (1) (2)) (3 (2.5 (2.5) (3)) (4)))
(2 (1 (1) (2)) (3 (2.5 (2.5) (3)) (4))) Removal of elements is handled by the following family of functions:
(defun BST-remove (B E)
"Remove E from BST B."
(if (BST-empty-p B)
B
(if (bin-tree-leaf-p B)
(BST-leaf-remove B E)
(BST-node-remove B E))))
(defun BST-leaf-remove (L E)
"Remove E from BST leaf L."
(if (= E (bin-tree-leaf-element L))
(make-empty-BST)
L))
(defun BST-node-remove (N E)
"Remove E from BST node N."
(let
((elmt (bin-tree-node-element N))
(left (bin-tree-node-left N))
(right (bin-tree-node-right N)))
(if (<= E elmt)
(if (bin-tree-leaf-p left)
(if (= E (bin-tree-leaf-element left))
right
N)
(make-bin-tree-node elmt (BST-node-remove left E) right))
(if (bin-tree-leaf-p right)
(if (= E (bin-tree-leaf-element right))
left
N)
(make-bin-tree-node elmt left (BST-node-remove right E))))))
This time, removal from empty BST's and BST's with a single leaf are both degenerate cases. The recursive removal algorithm deals with BST nodes. Traversing down the index nodes, the recursive algorithm searches for the parent node of the leaf to be removed. In case it is found, the sibling of the leaf to be removed replaces its parent node. For example, the effect of removing 2 from the BST represented by (2 (1 (1) (2)) (3 (3) (4))) is depicted as follows:
2 2
/ \ / \
/ \ / \
/ \ ==> / \
1 3 1 4
/ \ / \ / \
1 2 3 4 1 2
A trace of the deletion operation is given below: USER(4): (trace BST-remove BST-node-remove) (BST-NODE-REMOVE BST-REMOVE) USER(5): (BST-remove '(2 (1 (1) (2)) (3 (3) (4))) 3)
0: (BST-REMOVE (2 (1 (1) (2)) (3 (3) (4))) 3)
1: (BST-NODE-REMOVE (2 (1 (1) (2)) (3 (3) (4))) 3)
2: (BST-NODE-REMOVE (3 (3) (4)) 3)
2: returned (4)
1: returned (2 (1 (1) (2)) (4))
0: returned (2 (1 (1) (2)) (4))
(2 (1 (1) (2)) (4)))) ()) (4 () (5 () ())))
http://www.cs.sfu.ca/CC/310/pwfong/Lisp/3/tutorial3.html