16 Trees
17 Key concepts
17.0.1 Trees, tree representation
The key concepts in the context of trees and tree representation are:
- Node: The basic building block of a tree, which contains some data and one or more links to other nodes.
- Root: The topmost node in a tree, which has no parent node.
- Parent and child nodes: Nodes in a tree can have one or more child nodes and a single parent node.
- Leaf nodes: Nodes in a tree that have no child nodes.
- Depth: The number of edges from the root to a given node in the tree.
- Height: The number of edges from a given node to the deepest leaf node in the tree.
- Binary tree: A tree in which each node can have at most two child nodes.
- Binary search tree: A binary tree in which the left child of a node contains only values less than the node’s value, and the right child contains only values greater than the node’s value.
- Traversal: The process of visiting all nodes in a tree in a specific order, such as in-order, pre-order, or post-order traversal.
- Tree representation: Trees can be represented using various data structures, such as arrays, linked lists, or dynamically allocated memory.
Trees are a widely used data structure in computer science that are used to represent a hierarchical structure of data. A tree consists of nodes that are connected by edges, with the topmost node being called the root node. Each node can have zero or more child nodes, and a node that has no child nodes is called a leaf node.
The depth of a node in a tree is the number of edges from the root to the node, while the height of a node is the number of edges from the node to the deepest leaf node. In a binary tree, each node can have at most two child nodes, and a binary search tree is a type of binary tree in which the left child of a node contains only values less than the node’s value, and the right child contains only values greater than the node’s value.
There are various ways to traverse a tree, such as in-order, pre-order, or post-order traversal, which determine the order in which nodes are visited. Traversing a tree is often necessary to perform operations such as searching, inserting, or deleting nodes in the tree.
Trees can be represented using various data structures, such as arrays, linked lists, or dynamically allocated memory. Each method has its own advantages and disadvantages, and the choice of data structure depends on the specific use case and requirements of the application. For example, if the size of the tree is known in advance and memory efficiency is a concern, an array-based representation might be a good choice. On the other hand, if the size of the tree is not known in advance and nodes need to be added or removed dynamically, a linked list-based representation might be more appropriate.
17.1 Binary trees, traversal
A binary tree is a type of tree data structure in which each node has at most two child nodes, which are referred to as the left child and the right child. The structure of a binary tree is such that each node can have zero, one or two children.
Binary trees can be used to solve a wide range of problems such as searching, sorting, and dynamic programming. They are also used as the foundation for more complex data structures such as heaps and binary search trees.
There are three common methods for traversing a binary tree, which are:
In-order traversal: In this method, the left subtree is first traversed recursively, followed by the root node, and then the right subtree is traversed recursively. The result is a sorted list of the values in the tree.
Pre-order traversal: In this method, the root node is visited first, followed by the left subtree recursively, and then the right subtree recursively.
Post-order traversal: In this method, the left subtree is first traversed recursively, followed by the right subtree recursively, and then the root node is visited.
Each traversal method has its own uses and applications, depending on the problem being solved. For example, in-order traversal is often used for searching and sorting, while pre-order traversal is useful for creating a copy of the tree.
Binary trees can also be used to represent a wide range of data structures such as expression trees, binary search trees, and heaps. They are a fundamental data structure in computer science and are used extensively in many applications.
17.2 Binary search trees, insert, search, delete
Binary search tree is a binary tree data structure in which each node has a value and two child nodes, referred to as the left and right subtrees. The left subtree of a node contains only values less than the node’s value, while the right subtree contains only values greater than the node’s value.
To insert a new node into a binary search tree, we start at the root node and compare the value of the new node with the value of the current node. If the new node’s value is less than the current node’s value, we move to the left subtree, and if the new node’s value is greater than the current node’s value, we move to the right subtree. We continue this process until we reach a leaf node where we can insert the new node.
To search for a node in a binary search tree, we start at the root node and compare the value of the node with the value of the current node. If the value of the node is less than the current node’s value, we move to the left subtree, and if the value of the node is greater than the current node’s value, we move to the right subtree. We continue this process until we find the node or reach a leaf node where the node is not present in the tree.
To delete a node from a binary search tree, we first search for the node to be deleted. If the node has no children, we simply remove the node from the tree. If the node has only one child, we replace the node with its child. If the node has two children, we replace the node with its successor, which is the smallest value in its right subtree, and then delete the successor node.
Deleting a node from a binary search tree can also lead to imbalanced trees, where one subtree is much larger than the other. To maintain balance in the tree, we can use techniques such as tree rotation or AVL trees.
18 Learning outcomes
18.1 Understand how to implement a tree
Here is the pseudocode implementation of a binary search tree:
class Node
value
left
right
class BinarySearchTree
root
function insert(value)
new_node = Node(value)
if root is null
root = new_node
return
current_node = root
while true
if value == current_node.value
return
if value < current_node.value
if current_node.left is null
current_node.left = new_node
return
current_node = current_node.left
else
if current_node.right is null
current_node.right = new_node
return
current_node = current_node.right
function search(value)
if root is null
return false
current_node = root
while current_node is not null
if value == current_node.value
return true
if value < current_node.value
current_node = current_node.left
else
current_node = current_node.right
return false
function delete(value)
if root is null
return null
function find_min(node)
while node.left is not null
node = node.left
return node
function remove(node, value)
if node is null
return null
if value == node.value
if node.left is null and node.right is null
return null
if node.left is null
return node.right
if node.right is null
return node.left
temp = find_min(node.right)
node.value = temp.value
node.right = remove(node.right, temp.value)
else if value < node.value
node.left = remove(node.left, value)
else
node.right = remove(node.right, value)
return node
root = remove(root, value)Here is an example implementation of a binary search tree in Python:
class Node:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
class BinarySearchTree:
def __init__(self):
self.root = None
def insert(self, value):
new_node = Node(value)
if not self.root:
self.root = new_node
return
current_node = self.root
while True:
if value == current_node.value:
return
if value < current_node.value:
if not current_node.left:
current_node.left = new_node
return
current_node = current_node.left
else:
if not current_node.right:
current_node.right = new_node
return
current_node = current_node.right
def search(self, value):
if not self.root:
return False
current_node = self.root
while current_node:
if value == current_node.value:
return True
if value < current_node.value:
current_node = current_node.left
else:
current_node = current_node.right
return False
def delete(self, value):
if not self.root:
return None
def find_min(node):
while node.left:
node = node.left
return node
def remove(node, value):
if not node:
return None
if value == node.value:
if not node.left and not node.right:
return None
if not node.left:
return node.right
if not node.right:
return node.left
temp = find_min(node.right)
node.value = temp.value
node.right = remove(node.right, temp.value)
elif value < node.value:
node.left = remove(node.left, value)
else:
node.right = remove(node.right, value)
return node
self.root = remove(self.root, value)In this implementation, each node in the tree is represented by an instance of the Node class, which contains a value attribute and references to its left and right child nodes. The BinarySearchTree class contains methods for inserting a new node into the tree, searching for a node in the tree, and deleting a node from the tree.
The insert method first creates a new node with the given value and then traverses the tree, starting at the root node, to find the appropriate place to insert the new node based on the binary search tree property. The search method also traverses the tree to find the node with the given value, returning True if the node is found and False otherwise.
The delete method first searches for the node with the given value in the tree, and then removes it based on the type of children the node has. If the node has no children, it is simply removed. If the node has one child, the child node replaces the removed node. If the node has two children, the node is replaced with its successor and then the successor is removed.
This implementation demonstrates how to create and manipulate a binary search tree, a fundamental tree data structure in computer science.
18.2 Describe and trace different types of binary tree traversals using pseudocode
18.2.1 Inorder Traversal
function inorder(node):
if node is not null:
inorder(node.left)
visit(node)
inorder(node.right)In this traversal, the left subtree is recursively traversed first, then the current node is visited, and finally the right subtree is recursively traversed.
18.2.2 Preorder Traversal
function preorder(node):
if node is not null:
visit(node)
preorder(node.left)
preorder(node.right)18.2.3 Postorder Traversal
function postorder(node):
if node is not null:
postorder(node.left)
postorder(node.right)
visit(node)In this traversal, the left subtree is recursively traversed first, then the right subtree is recursively traversed, and finally the current node is visited.
To trace these traversals, let’s use the following binary tree as an example:
1
/ \
2 3
/ \ \
4 5 6Using the inorder traversal, we would visit the nodes in the order: 4, 2, 5, 1, 3, 6.
Using the preorder traversal, we would visit the nodes in the order: 1, 2, 4, 5, 3, 6.
Using the postorder traversal, we would visit the nodes in the order: 4, 5, 2, 6, 3, 1.
These pseudocode implementations demonstrate how to traverse binary trees, a fundamental data structure in computer science.
18.3 Describe and trace binary search tree operations using pseudocode
Here is the pseudocode for the different operations on a binary search tree:
18.3.1 Insertion
function insert(node, value):
if node is null:
return createNode(value)
if value < node.value:
node.left = insert(node.left, value)
else:
node.right = insert(node.right, value)
return nodeIn this operation, we traverse the tree recursively and insert the new value in the correct position based on its value compared to the values of the nodes already in the tree.
18.3.2 Search
function search(node, value):
if node is null or node.value == value:
return node
if value < node.value:
return search(node.left, value)
else:
return search(node.right, value)18.3.3 Deletion
function delete(node, value):
if node is null:
return null
if value < node.value:
node.left = delete(node.left, value)
else if value > node.value:
node.right = delete(node.right, value)
else:
if node.left is null:
return node.right
if node.right is null:
return node.left
temp = minNodeValue(node.right)
node.value = temp
node.right = delete(node.right, temp)
return nodeIn this operation, we traverse the tree recursively and delete the node with the given value if it exists in the tree. There are three cases: the node has no children, the node has one child, or the node has two children. In the third case, we replace the node with the smallest value in the right subtree, and then delete that node.
To trace these operations, let’s use the following binary search tree as an example:
8
/ \
3 10
/ \ \
1 6 14
/ \ /
4 7 13Using the insert operation, let’s insert the value 5 into the tree. This would result in the following binary search tree:
8
/ \
3 10
/ \ \
1 6 14
/ \ /
4 7 13
\
5Using the search operation, let’s search for the value 7 in the tree. This would return the node with the value 7.
Using the delete operation, let’s delete the value 6 from the tree. This would result in the following binary search tree:
8
/ \
3 10
/ \ \
1 5 14
/ /
4 13These pseudocode implementations demonstrate how to perform operations on a binary search tree, a widely used data structure in computer science.