Algorithms For Dummies

  Arranging and Searching Data 

     145

 

»

Creating the required structures requires fewer resources because binary 

heaps rely on arrays, making them cache friendlier as well.

 

»

Building a binary heap requires O(n) time, contrasted to BST, which requires 

O(n log n) time.

 

»

Using pointers to implement the tree isn’t necessary.

 

»

Relying on binary heap variations (for example, the Fibonacci Heap) offers 

advantages such as increase and decrease key times of O(1) time.

Building a binary search tree

You can build a BST using a variety of methods. Some people simply use a diction-

ary;  others  use  custom  code  (see  the  article  at 

https://interactivepython.

org/courselib/static/pythonds/Trees/SearchTreeImplementation.html

 

and 

http://code.activestate.com/recipes/577540-python-binary-search- 

tree/

 as examples). However, most developers don’t want to reinvent the wheel 

when it comes to BST. With this in mind, you need a package, such as 

bintrees

, 

which provides all the required functionality to create and interact with BST using 

a minimum of code. To download and install 

bintrees

, open a command prompt, 

type  pip install bintrees, and press Enter. You see 

bintrees

 installed on your 

system. The documentation for this package appears at 

https://pypi.python.

org/pypi/bintrees/2.0.6

.

You can use 

bintrees

 for all sorts of needs, but the example in this section looks 

specifically at a BST. In this case, the tree is unbalanced. The following code shows 

how to build and display a BST using 

bintrees

. (You can find this code in the 

A4D; 

07; Search Techniques.ipynb

 file on the Dummies site as part of the download-

able code; see the Introduction for details.)

from bintrees import BinaryTree

  

data = {3:'White', 2:'Red', 1:'Green', 5:'Orange',

        4:'Yellow', 7:'Purple', 0:'Magenta'}

  

tree = BinaryTree(data)

tree.update({6:'Teal'})

  

def displayKeyValue(key, value):

    print('Key: ', key, 'Value: ', value)

  

tree.foreach(displayKeyValue)

print('Item 3 contains: ', tree.get(3))

print('The maximum item is: ', tree.max_item())

  

---

146

 

   

  PART 2