10. Balanced Binary Search Trees

In chapter 6 binary search trees were defined along with a recursive insert algorithm. The discussion of binary search trees pointed out they have problems in some cases. Binary search trees can become unbalanced, actually quite often. When a tree is unbalanced the complexity of insert, delete, and lookup operations can get as bad as \Theta(n). This problem with unbalanced binary search trees was the motivation for the development of height-balanced AVL trees by G. M. Adelson-Velskii and E. M. Landis, two Soviet computer scientists, in 1962. AVL trees were named for these two inventors. Their paper on AVL trees [AVL62] described the first algorithm for maintaining balanced binary search trees. The chapter goes on to discuss Splay Trees as another example of balanced binary search trees.

10.1. AVL Tree Implementations

AVL trees maintain their own balance. The balance can be maintained in one of two ways. Either the height of each node in the tree can be maintained or the balance of each node in the tree can be maintained. If maintaining the height, there is a little more work to be done to adjust heights all the way up the tree. If balance is maintained then the code gets a little trickier, but there balances only need to be adjusted up to a pivot node.

In addition, AVL trees can be implemented with recursive or iterative insert and delete methods. Both are described in the text.

10.1.1. Iteratively Implemented AVL Tree

You can download avltree.py to work on an iterative implementation of AVL Trees.

  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
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
'''
  File:  avltree.py 
  Author: Steve Hubbard,  and 
  Date:  
  Description:  This module provides the AVLNode and AVLTree classes.
'''

from person import Person
from stack import Stack

class AVLNode:
   def __init__(self, item, balance = 0):
      self.item = item
      self.left = None
      self.right = None
      self.balance = balance
      
   def __str__(self):
      '''  This performs an inorder traversal of the tree rooted at self, 
         using recursion.  Return the corresponding string.
      '''
      st = str(self.item) + ' ' + str(self.balance) + '\n'
      if self.left != None:
         st = str(self.left) +  st  # A recursive call: str(self.left)
      if self.right != None:
         st = st + str(self.right)  # Another recursive call
      return st
   
   def rotateLeft(self):
      '''  Perform a left rotation of the subtree rooted at the
       receiver.  Answer the root node of the new subtree.  
      '''
      child = self.right
      if (child == None):
         print( 'Error!  No right child in rotateLeft.' )
         return None  # redundant
      else:
         self.right = child.left
         child.left = self
         return child

   def rotateRight(self):
      '''  Perform a right rotation of the subtree rooted at the
       receiver.  Answer the root node of the new subtree.  
      '''
      child = self.left
      if (child == None):
         print( 'Error!  No left child in rotateRight.' )
         return None  # redundant
      else:
         self.left = child.right
         child.right = self
         return child

   def rotateRightThenLeft(self):
      '''Perform a double inside left rotation at the receiver.  We
       assume the receiver has a right child (the bad child), which has a left 
       child. We rotate right at the bad child then rotate left at the pivot 
       node, self. Answer the root node of the new subtree.  We call this 
       case 3, subcase 2.
      '''
      pass
      
   def rotateLeftThenRight(self):
      '''Perform a double inside right rotation at the receiver.  We
       assume the receiver has a left child (the bad child) which has a right 
       child. We rotate left at the bad child, then rotate right at 
       the pivot, self.  Answer the root node of the new subtree. We call this 
       case 3, subcase 2.
      '''
      pass
   
class AVLTree:
   def __init__(self):
      self.root = None
      self.count = 0
      
   def __str__(self):
      st = 'There are ' + str(self.count) + ' nodes in the AVL tree.\n'
      return  st + str(self.root)  # Using the string hook for AVL nodes
   
   def insert(self, newItem):
      '''  Add a new node with item newItem, if there is not a match in the 
        tree.  Perform any rotations necessary to maintain the AVL tree, 
        including any needed updates to the balances of the nodes.  Most of the 
        actual work is done by other methods.
      '''
      pass

   def adjustBalances(self, theStack, pivot, newItem):
      '''  We adjust the balances of all the nodes in theStack, up to and
         including the pivot node, if any.  Later rotations may cause
         some of the balances to change.
      '''
      pass         
      
   def case1(self, theStack, pivot, newItem):
      '''  There is no pivot node.  Adjust the balances of all the nodes
         in theStack.
      '''
      self.adjustBalances(theStack, pivot, newItem)
            
   def case2(self, theStack, pivot, newItem):
      ''' The pivot node exists.  We have inserted a new node into the
         subtree of the pivot of smaller height.  Hence, we need to adjust 
         the balances of all the nodes in the stack up to and including 
         that of the pivot node.  No rotations are needed.
      '''
      self.adjustBalances(theStack, pivot, newItem)
            
   def case3(self, theStack, pivot, newItem):
      '''  The pivot node exists.  We have inserted a new node into the
         larger height subtree of the pivot node.  Hence rebalancing and 
         rotations are needed.
      '''
      self.adjustBalances(theStack, pivot, newItem)
      # Lots more!!!!
         
   def search(self, newItem):
      '''  The AVL tree is not empty.  We search for newItem. This method will 
        return a tuple: (pivot, theStack, parent, found).  
        In this tuple, if there is a pivot node, we return a reference to it 
        (or None). We create a stack of nodes along the search path -- theStack. 
        We indicate whether or not we found an item which matches newItem.  We 
        also return a reference to the last node the search examined -- referred
        to here as the parent.  (Note that if we find an object, the parent is 
        reference to that matching node.)  If there is no match, parent is a 
        reference to the node used to add a child in insert().
      '''
      pass
            
            
def main():
   print("Our names are ")
   print()
   a = AVLNode(20, -1)
   b = AVLNode( 30, -1)
   c = AVLNode(-100)
   d = AVLNode(290)
   '''
   print(a)
   print(b)
   '''
   t = AVLTree()
   t.root = b
   b.left = a
   a.left = c
   b.right = d
   t.count = 4
   print(t)
              
   a = AVLNode(50)
   b = AVLNode(30)
   c = AVLNode(40)
   a.left = b
   b.right = c
   print("Testing rotateLeftThenRight()")
   print(a.rotateLeftThenRight())
              
   (pivot, theStack, parent, found) = t.search(-70)
   print(pivot.item, parent.item, found)
   print()
   print("The items in the nodes of the stack are: ")
   while not theStack.isEmpty():
      current = theStack.pop()
      print(current.item)
   print()

   (pivot, theStack, parent, found) = t.search(25)
   print(pivot.item, parent.item, found)
   
   (pivot, theStack, parent, found) = t.search(-100)
   print(pivot.item, parent.item, found)
   
if __name__ == '__main__': main()
'''  The output from main():
[evaluate avltree.py]
Our names are
There are 4 nodes in the AVL tree.
-100 0
20 -1
30 -1
290 0

Testing rotateLeftThenRight()
30 0
40 0
50 0

20 -100 False

The items in the nodes of the stack are: 
-100
20
30

20 20 False
20 -100 True
'''

10.1.2. Recursively Implemented AVL Tree

AVL trees may also be implemented recursively meaning that the insert and delete methods can be written recursively. The outline of this implementation can be seen in the text. It is relatively short and is not provided for download.

10.2. Splay Tree Implementations

Splay trees do not maintain the balance or height. Instead they rely on rotations that always rotate a inserted or accessed element to the root of the tree. In doing this they maintain a balance in the tree, often exploiting spatial locality. Again, splay trees may be implemented recursively or iteratively.

10.2.1. Iteratively Implemented Splay Tree

You can download splaytree.py to work on an iterative implementation of splay trees. To run this program you will need to download stack.py module and you’ll need to download person.py module.

  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
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
'''
 File: splaytree.py
 Author(s): Steve Hubbard and 
 Date: 9/17/13
 Description: This module implements the SplayTree class and the
   SplayNode class.  The classes use bottom up splaying rather than 
   top down splaying.  We do not allow duplicate objects in the tree.
'''

from person import Person
from copy import deepcopy
from stack import Stack

class SplayNode:
   ''' This module implements the SplayNode class. This
     class in turn is used by the SplayTree class.  The classes
     use bottom up splaying rather than top down splaying.  We
     do not allow duplicate objects in the tree.
   '''
   
   def __init__(self, item, left = None, right = None):
      self.left = left
      self.item = item
      self.right = right

   def __str__(self): 
      st = '('
      if (self.left == None):
         st += '*'
      else:
         st += str(self.left) # recursion
      st += str(self.item)
      if (self.right == None):
         st += '*'
      else:
         st += str(self.right) # recursion
      st += ')'
      return st
   
   def inorder(self):
      ''' Perform an inorder traversal of the subtree rooted at
        the receiver.  Print each item in this subtree during
        the traversal.  This is done with recursion.
      '''
      pass
      
   def insertInNode(self, anItem):
      ''' Try to insert a copy of anItem into the bottom up splay
       tree rooted at the receiver.  If anItem is already in the tree,
       do not insert an extra copy. In any case, splay the new node,
       or the last node on the search path, to the root.  The method
       will answer a tuple.  The first element is True or False
       according to whether a new element was added or not.  The
       second element is the new root node.
       '''
       pass
   
   def rotateLeft(self):
      '''  Perform a left rotation of the subtree rooted at the
       receiver.  Answer the root node of the new subtree.  
      '''
      child = self.right
      if (child == None):
         print( 'Error!  No right child in rotateLeft. ' )
         return None  # redundant
      else:
         self.right = child.left
         child.left = self
         return child

   def splayToRoot(self, stack):
      '''  Perform a bottom up splay beginning at the node at the
       top of the stack.  Answer the root of the new tree.
      '''
      pass
      
   '''  Many more methods! '''
      

class SplayTree:
   
   def __init__(self):
      self.size = 0
      self.root = None

   def __str__(self):
      if self.root != None:
         return str(self.root)
      else:
         return ""
   
   def delete(self, anItem):
      '''  Atempt to find a match (==) for anItem in the receiver.
      If found, splay the corresponding node to the root and answer
      the item of the node. If not found, splay the last node on
      the search path to the root. In this case, answer None.  If
      found, we remove the node and make the largest element of the
      new left subtree (from the splaying of the node to the root
      position) the new root node of the tree.  Of course finding
      the largest element uses a splaying on that left subtree.
      If there is no left subtree, the right subtree becomes the
      root.  This may leave us with an empty tree.  If found,
      decrement the size of the tree and answer the item deleted.
      If not found, answer None.
      '''
      pass

   def findMax(self):
      ''' Find the largest element in the splay tree.  Splay that
      element to the root.  Answer a deep copy of the element.
      If the tree is empty, answer None.
      '''
      pass 

   def findMin(self):
      ''' Find the smallest element in the splay tree.  Splay that
      element to the root.  Answer a deep copy of the element.  If
      the tree is empty, answer None.
      '''
      if (self.root == None):
         return None
      self.root = self.root.findMin()
      return deepcopy(self.root.getItem())

   def getSize(self):
      return self.size

   def inorder(self):
      ''' Print the contents of the receiver, in inorder.
        Print one item per line.
      '''
      if self.root != None:
         self.root.inorder()

   def insert(self, anItem):
      ''' Insert a deep copy of anItem into the bottom up splay tree.
      If anItem is already present in the tree, do not insert a new 
      copy of anItem.  If anItem is added, increment the size of
      the receiver.  In either case, we splay from
      the last node.  If anItem was added, answer anItem.  If not,
      answer None.
      '''
      pass
         
   def retrieve(self, anItem):
      pass

   def update(self, anItem):
      pass


def main():
   
   print('My name is ')
   print('Test the SplayNode class: ')
   
   a = SplayNode(20, SplayNode(10), SplayNode(25))
   b = SplayNode(40, SplayNode(35), SplayNode(45))
   c = SplayNode(30, a, b)
   x = c.rotateLeft()
   print( x )
   print( str(x) == '((((*10*)20(*25*))30(*35*))40(*45*))' )
   print( '' )

   a = SplayNode(20, SplayNode(10), SplayNode(25))
   b = SplayNode(40, SplayNode(35), SplayNode(45))
   c = SplayNode(30, a, b)
   x = c.rotateRight()
   print( x )
   print( str(x) == '((*10*)20((*25*)30((*35*)40(*45*))))' )
   print( '' )
   
   a = SplayNode(20, SplayNode(10), SplayNode(25))
   b = SplayNode(40, SplayNode(35), SplayNode(45))
   c = SplayNode(30, a, b)
   d = SplayNode(60, SplayNode(55), SplayNode(65))
   e = SplayNode(90, SplayNode(80), SplayNode(100))
   f = SplayNode(70, d, e)
   root = SplayNode(50, c, f)
   print( root )
   print( '' )

   a = SplayNode(20, SplayNode(10), SplayNode(25))
   b = SplayNode(40, SplayNode(35), SplayNode(45))
   c = SplayNode(30, a, b)
   d = SplayNode(60, SplayNode(55), SplayNode(65))
   e = SplayNode(90, SplayNode(80), SplayNode(100))
   f = SplayNode(70, d, e)
   root = SplayNode(50, c, f)
   x = root.rotateRightThenLeft()
   print( x )
   print( str(x) ==  \
   '(((((*10*)20(*25*))30((*35*)40(*45*)))50(*55*))60((*65*)70((*80*)90(*100*))))' )
   print( '' )

   a = SplayNode(20, SplayNode(10), SplayNode(25))
   b = SplayNode(40, SplayNode(35), SplayNode(45))
   c = SplayNode(30, a, b)
   d = SplayNode(60, SplayNode(55), SplayNode(65))
   e = SplayNode(90, SplayNode(80), SplayNode(100))
   f = SplayNode(70, d, e)
   root = SplayNode(50, c, f)
   x = root.rotateLeftThenRight()
   print( x )
   print( str(x) ==  \
   '((((*10*)20(*25*))30(*35*))40((*45*)50(((*55*)60(*65*))70((*80*)90(*100*)))))' )
   print( '' )

   a = SplayNode(20, SplayNode(10), SplayNode(25))
   b = SplayNode(40, SplayNode(35), SplayNode(45))
   c = SplayNode(30, a, b)
   d = SplayNode(60, SplayNode(55), SplayNode(65))
   e = SplayNode(90, SplayNode(80), SplayNode(100))
   f = SplayNode(70, d, e)
   root = SplayNode(50, c, f)
   x = root.doubleRotateLeft()
   print( x )
   print( str(x) ==  \
   '((((((*10*)20(*25*))30((*35*)40(*45*)))50((*55*)60(*65*)))70(*80*))90(*100*))' )
   print( '' )
   
   a = SplayNode(20, SplayNode(10), SplayNode(25))
   b = SplayNode(40, SplayNode(35), SplayNode(45))
   c = SplayNode(30, a, b)
   d = SplayNode(60, SplayNode(55), SplayNode(65))
   e = SplayNode(90, SplayNode(80), SplayNode(100))
   f = SplayNode(70, d, e)
   root = SplayNode(50, c, f)
   x = root.doubleRotateRight()
   print( x )
   print( str(x) == \
   '((*10*)20((*25*)30(((*35*)40(*45*))50(((*55*)60(*65*))70((*80*)90(*100*))))))' )
   print( '' )
   
   a = SplayNode(20, SplayNode(10), SplayNode(25))
   b = SplayNode(40, SplayNode(35), SplayNode(45))
   c = SplayNode(30, a, b)
   d = SplayNode(60, SplayNode(55), SplayNode(65))
   e = SplayNode(90, SplayNode(80), SplayNode(100))
   f = SplayNode(70, d, e)
   root = SplayNode(50, c, f)
   x = root.find(35)
   print( x )
   print( str(x) == \
   '((((*10*)20(*25*))30*)35((*40(*45*))50(((*55*)60(*65*))70((*80*)90(*100*)))))')

   print('Test the SplayTree class: ')
   t = SplayTree()
   t.insert(1)
   t.insert(2)
   t.insert(3)
   t.insert(4)
   t.insert(5)
   t.insert(6)
   t.insert(7)
   t.retrieve(1)
   print( str(t) == '(*1(((*2(*3*))4(*5*))6(*7*)))')
   print( 'The size of the tree is ' + str(t.getSize()) )
   
   t = SplayTree()
   t.insert(1)
   t.insert(2)
   t.insert(3)
   t.insert(4)
   t.insert(5)
   t.insert(6)
   t.insert(7)
   t.findMin()
   print( str(t) ==  '(*1(((*2(*3*))4(*5*))6(*7*)))')
   
   t = SplayTree()
   t.insert(1)
   t.insert(2)
   t.insert(3)
   t.insert(4)
   t.insert(5)
   t.insert(6)
   t.insert(7)
   t.retrieve(1)
   t.delete(3)
   print( str(t) ==  '((*1*)2((*4(*5*))6(*7*)))' )
   
   t = SplayTree()
   t.insert(1)
   t.insert(2)
   t.insert(3)
   t.insert(4)
   t.insert(5)
   t.insert(6)
   t.insert(7)
   t.retrieve(1)
   t.delete(3)
   t.findMax()
   print( str(t) == '((((*1*)2(*4(*5*)))6*)7*)')

   t = SplayTree()
   t.insert(Person('Joe', 25))
   t.insert(Person('Jill',35))
   t.insert(Person('Jon',15))
   t.insert(Person('Jack',25))
   t.insert(Person('John',30))
   t.insert(Person('Jud',95))
   t.insert(Person('Joey',27))
   st = str(t) + '\n'
   t.update(Person('James', 25))
   st += str(t) + '\n'
   x = t.retrieve(Person('',15))
   st += str(x) + '\n'
   st += str(t) + '\n'
   x = t.delete(Person('', 35))
   st += str(x) + '\n'
   st += str(t) + '\n'
   x = t.findMax()
   st += str(x) + '\n'
   st += str(t) + '\n'
   print( t )

   print( 'The size of the tree is ' + str(t.getSize()) )

   t = SplayTree()
   t.insert(1)
   t.insert(2)
   t.insert(3)
   t.insert(4)
   t.insert(5)
   t.insert(6)
   t.insert(7)
   t.insert(3.5)
   print( str(t) == '((((*1*)2*)3*)3.5(((*4*)5(*6*))7*))' )
   
   t = SplayTree()
   t.insert(1)
   t.insert(2)
   t.insert(3)
   t.insert(4)
   t.insert(5)
   t.insert(6)
   t.insert(7)
   t.insert(3.5)
   t.delete(3.5)
   print( str(t) == '(((*1*)2*)3(((*4*)5(*6*))7*))')
   print( 'The size of the tree is ' + str(t.getSize()) )
   

   t = SplayTree()
   t.insert(3)
   t.insert(2)
   t.insert(1)
   t.delete(1)
   print( 'The size of the tree is ' + str(t.getSize()) )

   t = SplayTree()
   t.insert(Person('Joe', 25))
   t.insert(Person('Jill',35))
   t.insert(Person('Jon',15))
   t.insert(Person('Jack',25))
   t.insert(Person('John',30))
   t.insert(Person('Jud',95))
   t.insert(Person('Joey',27))
   t.inorder()
      
if __name__ == '__main__': main()

''' Output, from splaytree.py, wrapped around!
[evaluate splaytree.py]
My name is 
Test the SplayNode class: 
((((*10*)20(*25*))30(*35*))40(*45*))
True

((*10*)20((*25*)30((*35*)40(*45*))))
True

((((*10*)20(*25*))30((*35*)40(*45*)))50(((*55*)60(*65*))70((*80*)90(*100*))))

(((((*10*)20(*25*))30((*35*)40(*45*)))50(*55*))60((*65*)70((*80*)90(*100*))))
True

((((*10*)20(*25*))30(*35*))40((*45*)50(((*55*)60(*65*))70((*80*)90(*100*)))))
True

((((((*10*)20(*25*))30((*35*)40(*45*)))50((*55*)60(*65*)))70(*80*))90(*100*))
True

((*10*)20((*25*)30(((*35*)40(*45*))50(((*55*)60(*65*))70((*80*)90(*100*))))))
True

((((*10*)20(*25*))30*)35((*40(*45*))50(((*55*)60(*65*))70((*80*)90(*100*)))))
True
Test the SplayTree class: 
True
The size of the tree is 7
True
True
True
((((*Name: Jon Id: 15 (*Name: James Id: 25 *))Name: Joey Id: 27 *)
                                   Name: John Id: 30 *)Name: Jud Id: 95 *)
The size of the tree is 5
True
True
The size of the tree is 7
The size of the tree is 2
Name: Jon Id: 15 
Name: Joe Id: 25 
Name: Joey Id: 27 
Name: John Id: 30 
Name: Jill Id: 35 
Name: Jud Id: 95 

'''
   
      
   
      

10.2.2. Recursively Implemented Splay Tree

A recursive implementation of splay trees relies on keeping track of the left or right double rotations as the recursive insert or lookup returns up the tree. To accomplish this you must call a rotate function. Calling rotate[“RL”](pivot) would call the rotate right then left double rotation. The rotate variable is a dictionary (i.e. hash table) in the code provided here.

You can download splay.py file to begin working on the recursive splay tree implementation.

  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
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
'''
 File: splay.py
 Author: Kent D. Lee
 Date: 8/21/2014
 Description: This module implements the SplayTree class. This
   class uses the SplayNode class.  The classes
   use bottom up splaying rather than top down splaying.  We
   do not allow duplicate objects in the tree.

   Delete is not implemented in this file currently. Test code
   should be added to thoroughly test insert, lookup, and delete. 
   Recall that looking up a value rotates it to the root. Deleting 
   an item rotates its parent to the root. 
'''

def rotateLeft(pivot):
   pass

def rotateRight(pivot):
   pass

def rotateRL(pivot):
   pass

def rotateLR(pivot):
   pass

def rotateRR(pivot):
   pass

def rotateLL(pivot):
   pass

rotate = {}
rotate["RL"] = rotateRL
rotate["LR"] = rotateLR
rotate["RR"] = rotateRR
rotate["LL"] = rotateLL

singleRotate = {}
singleRotate["R"] = rotateRight
singleRotate["L"] = rotateLeft

class SplayTree:

   class SplayNode:
      def __init__(self, item, left=None, right=None):
         self.item = item
         self.left = left
         self.right = right
         
      def __str__(self):
         st = '('
         if (self.left == None):
            st += '*'
         else:
            st += str(self.left)
         st += str(self.item)
         if (self.right == None):
            st += '*'
         else:
            st += str(self.right)
         st += ')'
         return st

   def __init__(self):
      self.root = None
      self.rString = ""


   # Pass searching = True if just searching and not 
   # really inserting. If the item is found, true is 
   # returned. If the item is not found, an exception
   # containing false is raised. 

   def insert(self,item,searching=False):

      def __insert(root,item):
         ''' return the new root after inserting
             item into the tree currently rooted at 
             root. If searching for the value and not 
             inserting, then raise Exception(False) if 
             the item is not found. 
         '''

         return root

      self.found = False

      self.root = __insert(self.root,item)

      # Handle any single rotation that must 
      # be done after inserting the value. 
      if self.rString in singleRotate:
         self.root = singleRotate[self.rString](self.root)

      self.rString = ""

      return self.found

   def lookup(self,item):

      try:
         return self.insert(item,True)
      except Exception as inst:
         if inst.args[0] == False:
            return False

         raise Exception(inst)
            
   def __str__(self):
      if self.root != None:
         return str(self.root)
      else:
         return ""

def main():
   # This should print the following.
   #(*20*)
   #((*20*)30*)
   #(*5(*20(*30*)))
   #((*5*)8(*20(*30*)))
   #(((*5*)8((*20*)30*))42*)
   #(((*5*)8*)15((*20(*30*))42*))
   #(((*5*)8*)10(*15((*20(*30*))42*)))   
   t = SplayTree2()
   t.insert(20)
   print(str(t))
   t.insert(30)
   print(str(t))
   t.insert(5)
   print(str(t))
   t.insert(8)
   print(str(t))
   t.insert(42)
   print(str(t))
   t.insert(15)
   print(str(t))
   t.insert(10)   
   print(str(t))


if __name__ == '__main__': main()