Tree
Trees are the opposite of arrays and structures such as linked list hash tables, since the aforementioned are linear, and trees are not linear, since they can have 0 or more child nodes
A tree starts with a single node called root or a parent node and each child of the tree starts from this node we can notice in the previous example that a child node has only one parent node but a parent node can have several children, this relationship goes in one direction, it can go from parent to child or from child to parent.
Trees are very important as they are used a lot in computer science every day
Ejemplo
An example of trees is with the structure of html, although it is not a programming language you can see a similar structure to the trees. In Html we can say that the root node is the html tag this tag will have 2 children nodes that would be < body > and the < head > and so within these tags will have more children ... .
Another example would be the comments of a web page where each comment can be answered with another comment.
Tipos
There are a large number of tree types in computer science.
You can see in wikipedia this amountBinary Tree
A binary tree is a Tree data structure that has to follow certain rules:
A node must have a maximum of 2 child nodes
A child node cannot have more than one parent
In the previous image we can see that this node is not a binary tree since node L has more than 2 children
How does it work?Types of binary tree
You can consult how to identigy each node in this link.
The one we are interesed in creating is the Perfect binary tree, since it has most interesting properties and is much more efficient than most.
Some interesting properties
- you can calculate the number by the height 2^h - 1
Complexity of a Perfect binary tree
Binary tree unBalanced and Balanced
These binary trees as seen in the image of the binary tree types are unbalanced. This is a problem with binary trees since they can take this form. When taking this form it will have a higher complexity.
Since they will operate similar to a linked list.
When to use it?
The binary tree as we can see, when it is a perfect binary tree is the fastest data structure in all operations. We van also see that it is ordered. Therefore it is easy to imagine where each node is and how the structure is set up. It has a flexible size.
In general it is good to use it when we have data that fits in a balanced or perfect binary tree. (for example in a random list or in something relative)
When not to use it
One of the disadvantages is that no operation has O(1) complexity so if we are only going to use a list to add an element or remove a last or firts element it is better to use another data structure like linked list or Arrays
Implement it
It is easy to complement it, the difficult thing comes when an element is eliminated, since it has a structure a little difficult to understand.
class Node():
def __init__(self, data):
self.data = data
self.left = None
self.right = None
class BST():
def __init__(self):
self.root = None
self.number_of_nodes = 0
def insert(self, data):
new_node = Node(data)
if self.root == None:
self.root = new_node
self.number_of_nodes += 1
return
else:
current_node = self.root
while(current_node.left != new_node) and (current_node.right != new_node):
if new_node.data > current_node.data:
if current_node.right == None:
current_node.right = new_node
else:
current_node = current_node.right
elif new_node.data < current_node.data:
if current_node.left == None:
current_node.left = new_node
else:
current_node = current_node.left
self.number_of_nodes += 1
return
def search(self,data):
if self.root == None:
return "Tree Is Empty"
else:
current_node = self.root
while True:
if current_node == None:
return "Not Found"
if current_node.data == data:
return "Found"
elif current_node.data > data:
current_node = current_node.left
elif current_node.data < data:
current_node = current_node.right
def remove(self, data):
if self.root == None:
return "Tree Is Empty"
current_node = self.root
parent_node = None
while current_node!=None:
if current_node.data > data:
parent_node = current_node
current_node = current_node.left
elif current_node.data < data:
parent_node = current_node
current_node = current_node.right
else:
if current_node.right == None:
if parent_node == None:
self.root = current_node.left
return
else:
if parent_node.data > current_node.data:
parent_node.left = current_node.left
return
else:
parent_node.right = current_node.left
return
elif current_node.left == None:
if parent_node == None:
self.root = current_node.right
return
else:
if parent_node.data > current_node.data:
parent_node.left = current_node.right
return
else:
parent_node.right = current_node.right
return
elif current_node.left == None and current_node.right == None:
if parent_node == None:
current_node = None
return
if parent_node.data > current_node.data:
parent_node.left = None
return
else:
parent_node.right = None
return
elif current_node.left != None and current_node.right != None:
del_node = current_node.right
del_node_parent = current_node.right
while del_node.left != None:
del_node_parent = del_node
del_node = del_node.left
current_node.data = del_node.data
if del_node == del_node_parent:
current_node.right = del_node.right
return
if del_node.right == None:
del_node_parent.left = None
return
else:
del_node_parent.left = del_node.right
return
return "Not Found"
AVL Trees + Red Black Trees
these are very similar and very useful to balance a binary Tree since what they do is when an element is addedñade o se elimina un elemento, cambiara el orden de los nodos para balancearlos.
AVL Tree
The AVL tree takes its name from the initial of the sumames of its inventors, Georgii Adelson-Velskii y Yevgeniy Landis . They made it known in the publication of an article in 1962, «An algorithm for the organization of information» .
AVL trees are always balanced in such a way that for all nodes, the height of the left branch does not differ by more than one unit from the height of the right branch or vice versa. Thanks to this form of balancing, the complexity of a search in one of these trees is always kept in order of complexity O(log n).The balancing factor can be stored directly at each node or computed from the heights of the subtrees.
Red-black tree
A red-black tree is an abstract type of data. Specifically, it is balanced binary search tree, a data structure used in computer science and informatics. The original structure was created by Rudoll Bayer in 1972, who gave it the name "Symetric binary B-Trees", but it took its modern name in a paper by Leo J.Guibas and Rober done in 1978. It is complex, but has a good worst-case runtime for its operations and is efficient in practice. It can search, insert, and delete in O(log n) time, where n is the list elemnts in the tree.
Binary Heap
Are a particular and simple case of the Tree data structure and is based on a Binary tree balanced, which can be seen as a binary tree with two additional constraints
For more infoThis one, unlike the previous ones, is not ordered, so the search for an element will have a higher complexity.
What the binary heap does is to create a tree which is sorted in order.
Implementation
import sys
class MaxHeap:
def __init__(self, maxsize):
self.maxsize = maxsize
self.size = 0
self.Heap = [0] * (self.maxsize + 1)
self.Heap[0] = sys.maxsize
self.FRONT = 1
def parent(self, pos):
return pos // 2
def left_child(self, pos):
return 2 * pos
def right_child(self, pos):
return (2 * pos) + 1
def is_leaf(self, pos):
if pos >= (self.size // 2) and pos <= self.size:
return True
return False
def swap(self, fpos, spos):
self.Heap[fpos], self.Heap[spos] = self.Heap[spos], self.Heap[fpos]
def max_heapify(self, pos):
if not self.is_leaf(pos):
if (self.Heap[pos] < self.Heap[self.left_child(pos)] or
self.Heap[pos] < self.Heap[self.right_child(pos)]):
if self.Heap[self.left_child(pos)] > self.Heap[self.right_child(pos)]:
self.swap(pos, self.left_child(pos))
self.max_heapify(self.left_child(pos))
else:
self.swap(pos, self.right_child(pos))
self.max_heapify(self.right_child(pos))
def insert(self, element):
if self.size >= self.maxsize:
return
self.size += 1
self.Heap[self.size] = element
current = self.size
while self.Heap[current] > self.Heap[self.parent(current)]:
self.swap(current, self.parent(current))
current = self.parent(current)
def print_heap(self):
for i in range(1, (self.size // 2) + 1):
print(" PARENT : " + str(self.Heap[i]) + " LEFT CHILD : " +
str(self.Heap[2 * i]) + " RIGHT CHILD : " +
str(self.Heap[2 * i + 1]))
def extract_max(self):
popped = self.Heap[self.FRONT]
self.Heap[self.FRONT] = self.Heap[self.size]
self.size -= 1
self.max_heapify(self.FRONT)
return popped