A data structure is an efficient way to store and organize data with associated operations in order to take advantage as long as possible it. There are several data structures and, among them, this article will address one in particular: the binary search tree.
First of all, a tree is an abstraction used to stand for non-linear hierarchical structures. There are several types of trees such as: binary tree, AVL tree, red-black tree, B-tree, and so on.
A binary tree is a special type of tree in which each node can have zero, one, or at most two subtrees: the left and right subtrees. If the one doesn’t have any subtrees, it’s a leaf node.
Binary trees are very useful for modeling situations in which at each point in the process, it’s needs to take a decision between two directions.
There are three types of binary trees: strictly binary, full and complete; and they tell apart from each other by node’s the number of subtrees and by the node’s position in the tree.
Strictly binary: it’s the one in which the node always has or none (in the case of a leaf node) or two subtrees, that is, there is no internal node with only one child, all always have two.
Nearly complete: A nearly complete binary tree is a tree in which the height difference between the subtrees of any node is at most 1. In other words, each leaf node in the tree must be at either D or D-1.
Complete: it's a strictly binary tree in which all its leaf nodes are at the same level. In this type of tree, it’s possible to calculate the number of nodes per level, as well as the tree’s node total number.
Implementation Types
Generally, in the implementation a binary tree, there are two commonly used approaches:
- Using an array (static allocation).
- Using a linked list (dynamic allocation).
Which implementation to choose depends exclusively on the application and there is no one that is better than other one in all cases. Now, regardless of the type of implementation used, the following basic operations are possible:
- Tree creation.
- Insertion of an element.
- Removal of an element.
- Search for an element.
- Tree destruction.
- Obtaining information about the tree.
Introduced a little what trees are, now let’s go to the tree that is the title of this article. A binary search tree is a binary tree, therefore, it’s the same properties as a binary tree with the addition that each node has a value (key) associated with it in such a way that the value determines its position in the tree, that is, nodes is the left subtree have a numerical value lower than the root node (or parent node) and all nodes in the right subtree have a numerical value greater than the root node.
Node insertion and removal operations in the binary search tree must be performed respecting this node placement rule. It’s a great alternative to using arrays for binary search operations and has a dynamic structure.
The following are the costs associated with the main operations on a binary search tree containing N nodes. The worst case takes place when the tree isn’t balanced, that is, its height isn’t the minimum possible.
- Insertion: in the average case, O(log N) and in the worst case O(N).
- Removal: in the average case, O(log N) and in the worst case O(N).
- Search: in the average case, O(log N) and in the worst case O(N).
The following is a Python implementation of a binary search tree and its associated operations.
from typing import Union
class Node:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
def show(self) -> None:
print(self.value)
class BinarySearchTree:
def __init__(self):
self.root = None
self.links = []
def insert(self, value) -> None:
node = Node(value)
if not self.root:
self.root = node
else:
current = self.root
while True:
parent_node = current
if value < current.value:
current = current.left
if not current:
parent_node.left = node
self.links.append(str(parent_node.value) + '->' + str(node.value))
return
else:
current = current.right
if not current:
parent_node.right = node
self.links.append(str(parent_node.value) + '->' + str(node.value))
return
def search(self, value) -> Union[Node, None]:
current_node = self.root
while current_node.value != value:
if value < current_node.value:
current_node = current_node.left
else:
current_node = current_node.right
if not current_node:
return None
return current_node
# Root, lelf and right
def pre_order(self, node: Node) -> None:
if node:
print(node.value)
self.pre_order(node.left)
self.pre_order(node.right)
# Left, root, right
def in_order(self, node: Node) -> None:
if node:
self.in_order(node.left)
print(node.value)
self.in_order(node.right)
# Left, right, root
def pos_order(self, node: Node) -> Union[None, bool]:
if node:
self.pos_order(node.left)
self.pos_order(node.right)
print(node.value)
def delete(self, value) -> None:
if not self.root:
print('The tree is empty...')
return None
current_node = self.root
parent_node = self.root
_left = True
while current_node.value != value:
parent_node = current_node
if value < current_node.value:
_left = True
current_node = current_node.left
else:
_left = False
current_node = current_node.right
if not current_node:
return False
if not current_node.left and not current_node.right:
if current_node == self.root:
self.root = None
elif _left:
self.links.remove(str(parent_node.value) + '->' + str(current_node.value))
parent_node.left = None
else:
self.links.remove(str(parent_node.value) + '->' + str(current_node.value))
parent_node.right = None
elif not current_node.right:
self.links.remove(str(parent_node.value) + '->' + str(current_node.value))
self.links.remove(str(current_node.value) + '->' + str(current_node.left.value))
if current_node == self.root:
self.root = current_node.left
self.links.append(str(self.root.value) + '->' + str(current_node.left.value))
elif _left:
parent_node.left = current_node.left
self.links.append(str(parent_node.value) + '->' + str(current_node.left.value))
else:
parent_node.right = current_node.left
self.links.append(str(parent_node.value) + '->' + str(current_node.left.value))
elif not current_node.left:
self.links.remove(str(parent_node.value) + '->' + str(current_node.value))
self.links.remove(str(current_node.value) + '->' + str(current_node.right.value))
if current_node == self.root:
self.links.append(str(self.root.value) + '->' + str(current_node.right.value))
self.root = current_node.right
elif _left:
self.links.append(str(parent_node.value) + '->' + str(current_node.right.value))
parent_node.left = current_node.right
else:
self.links.append(str(parent_node.value) + '->' + str(current_node.right.value))
parent_node.right = current_node.right
else:
next = self.get_next(current_node)
self.links.remove(str(parent_node.value) + '->' + str(current_node.value))
self.links.remove(str(current_node.right.value) + '->' + str(next.value))
self.links.remove(str(current_node.value) + '->' + str(current_node.left.value))
self.links.remove(str(current_node.value) + '->' + str(current_node.right.value))
if current_node == self.root:
self.links.append(str(self.root.value) + '->' + str(next.value))
self.root = next
elif _left:
self.links.append(str(parent_node.value) + '->' + str(next.value))
parent_node.left = next
else:
self.links.append(str(parent_node.value) + '->' + str(next.value))
parent_node.right = next
self.links.append(str(next.value) + '->' + str(current_node.left.value))
self.links.append(str(next.value) + '->' + str(current_node.right.value))
next.left = current_node.left
return True
def get_next(self, node: Node):
next_parent = node
next = node
current = node.right
while current != None:
next_parent = next
next = current
current = current.left
if next != node.right:
next_parent.left = next.right
next.right = node.right
return next
if __name__ == "__main__":
tree = BinarySearchTree()
tree.insert(53)
tree.insert(30)
tree.insert(14)
tree.insert(39)
tree.insert(9)
tree.insert(23)
tree.insert(34)
tree.insert(49)
tree.insert(72)
tree.insert(61)
tree.insert(84)
tree.insert(79)
tree.pre_order(tree.root)
print('----------------')
tree.in_order(tree.root)
print('----------------')
tree.pos_order(tree.root)
print('----------------')
if tree.search(79):
print('Found value!')
else:
print('Not found value!')
There are many other data structures out there, worth looking into and learning more. The data structure presented here is just some of them. Well, that 's it! See you guys. 👋👨💻
Top comments (0)