Python: Array Implementation of a Binary Search Tree

Question

I've seen many types of linked-list implementations of binary search trees, and I am wondering how I would go about implementing one in an array. Is this possible? And how would it look like if it is? Thank you so much!

Here is an array implementation of a queue!

class Queue:

    MAX = 6

    def __init__(self):
        self.queue = [None for x in range(self.MAX)]
        self.front = 0
        self.rear = 0

    def isEmpty(self):
        return self.front == self.rear

    def size(self):
        if self.isEmpty():
            return 0
        elif self.front < self.rear:
            return self.rear - self.front
        else:
            return self.rear + self.MAX - self.front

    def isFull(self):
        return self.size() == self.MAX - 1

    def insert(self, data):
        if self.isFull():
            print("Cannot insert to full queue")
        else:
            self.queue[self.rear] = data
            self.rear = (self.rear + 1) % self.MAX
            return data


    def delete(self):
        if self.isEmpty():
            print("Cannot delete from empty queue")
        else:
            data = self.queue[self.front]
            self.queue[self.front] = None
            self.front = (self.front + 1) % self.MAX
            return data

    def peek(self):
        if self.isEmpty():
            return None
        else:
            return self.queue[self.front]

    def display(self):
        if self.isEmpty():
            print("Empty Queue")
        elif self.front < self.rear:
            for i in range(self.front, self.rear):
                print(self.queue[i], end = ' ')
        else:
            for i in range(self.front, self.MAX):
                print(self.queue[i], end = ' ')
            for j in range(self.rear):
                print(self.queue[j], end = ' ')

"Here is an array implementation of a queue" - is that relevant to your question ? — Nir Alfasi
– Nir Alfasi, Commented Sep 12, 2015 at 5:45
Why? What functionality do linked lists have that you need to reproduce in such a c-like manner? — Alea Kootz
– Alea Kootz, Commented Sep 12, 2015 at 6:12

strubbly · Accepted Answer · 2015-09-12 07:25:04Z

Your question is a little bit confused. A Queue is an abstract data type that can be implemented in more than one way. Implementing it in an array or list data structure is a standard implementation and straightforward as you can see.

A Binary Search Tree is already an implementation - typically an implementation of an abstract data type like an Ordered Map Container abstract data type. It depends on the ability to (efficiently) create and delete nodes with links to other nodes in them. You typically need to code this implementation in terms of primitives in your language that implement that sort of creation and deletion. Restricting yourself to the array type rules out those primitives.

However, most languages implement those primitives on top of a more primitive layer, your computer process address space (its memory). So you could pretend that the array is like a memory and implement your own allocation and deallocation mechanism on top of that array. Have a look at typical memory allocation algorithms to see what I am talking about.

Of course this is not a good idea in practice, but perhaps you are doing it as a learning experience. It will certainly require some learning!

One other note. You may be thinking about a Heap (as implemented in the Python heapq module). A Heap is not a Binary Search Tree but it has some similarities and is worth learning about.

laike9m · Accepted Answer · 2015-09-12 09:50:31Z

0

I've written BSTs, but I don't know how to do it using "array" or "linked list". Here's what me and other people normally do:

class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left = self.right = None

class Tree:
    def __init__(self):
        self.root = None

    def add_node(self, val):
        # traversing the tree by comparing val with existing node value
        ...

    def remove_node(self, val):
        # whatever...

You store TreeNode in a Tree.

answered Sep 12, 2015 at 9:50

laike9m

19.6k23 gold badges117 silver badges154 bronze badges

1 Comment

jbuddy_13 Over a year ago

I think this is what OP meant by a linked list implementation as in given TreeNode references other tree nodes through pointers. Whereas an array implementation is like geeksforgeeks.org/binary-tree-array-implementation Note-- this is a vanilla binary tree not a BST, but hopefully you get the gist.

Collectives™ on Stack Overflow

Python: Array Implementation of a Binary Search Tree

2 Answers 2

Comments

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related