CODEWITHSUNDEEP
pythonoop
Icy Peachy
Icy Peachy

Reputation: 31

Python: Array Implementation of a Binary Search Tree

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 = ' ')

Upvotes: 1

Views: 1434

Answers (2)

laike9m
laike9m

Reputation: 19368

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.

Upvotes: 0

strubbly
strubbly

Reputation: 3507

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.

Upvotes: 1

Related Questions