Data Structures & Algorithms – Trees (e.g. binary trees, AVL trees, B-trees)
Trees are a fundamental data structure used in computer science for various purposes such as searching, sorting, and data organization. There are many different types of trees, each with their own characteristics and use cases. In this section, we will explore three commonly used types of trees: binary trees, AVL trees, and B-trees.
- Binary Trees: A binary tree is a tree data structure in which each node has at most two children, which are referred to as the left child and the right child. A binary tree can be used to represent hierarchical relationships between data. Here is an example of how to implement a binary tree in Python:
class Node:
def __init__(self, data):
self.data = data
self.left = None
self.right = None
class BinaryTree:
def __init__(self):
self.root = None
def insert(self, data):
new_node = Node(data)
if self.root is None:
self.root = new_node
else:
current = self.root
while True:
if data < current.data:
if current.left is None:
current.left = new_node
break
else:
current = current.left
else:
if current.right is None:
current.right = new_node
break
else:
current = current.right
And here is an example of how to implement a binary tree in JavaScript:
class Node {
constructor(data) {
this.data = data;
this.left = null;
this.right = null;
}
}
class BinaryTree {
constructor() {
this.root = null;
}
insert(data) {
const newNode = new Node(data);
if (this.root === null) {
this.root = newNode;
} else {
let current = this.root;
while (true) {
if (data < current.data) {
if (current.left === null) {
current.left = newNode;
break;
} else {
current = current.left;
}
} else {
if (current.right === null) {
current.right = newNode;
break;
} else {
current = current.right;
}
}
}
}
}
}
And here is an example of how to implement a binary tree in Java:
class Node {
int data;
Node left;
Node right;
public Node(int data) {
this.data = data;
left = null;
right = null;
}
}
class BinaryTree {
Node root;
public BinaryTree() {
root = null;
}
public void insert(int data) {
Node newNode = new Node(data);
if (root == null) {
root = newNode;
return;
}
Node current = root;
while (true) {
if (data < current.data) {
if (current.left == null) {
current.left = newNode;
break;
} else {
current = current.left;
}
} else {
if (current.right == null) {
current.right = newNode;
break;
} else {
current = current.right;
}
}
}
}
}
And here is an example of how to implement a binary tree in Rust:
struct Node {
data: i32,
left: Option<Box<Node>>,
right: Option<Box<Node>>,
}
impl Node {
fn new(data: i32) -> Self {
Node {
data,
left: None,
right: None,
}
}
}
struct BinaryTree {
root: Option<Box<Node>>,
}
impl BinaryTree {
fn new() -> Self {
BinaryTree { root: None }
}
fn insert(&mut self, data: i32) {
let new_node = Box::new(Node::new(data));
match &mut self.root {
None => {
self.root = Some(new_node);
}
Some(current) => {
loop {
if data < current.data {
match &mut current.left {
None => {
current.left = Some(new_node);
break;
}
Some(node) => current = node,
}
} else {
match &mut current.right {
None => {
current.right = Some(new_node);
break;
}
Some(node) => current = node,
}
}
}
}
}
}
}
- AVL Trees: AVL trees are a type of self-balancing binary search tree. The balance factor of an AVL tree is the difference in height of its left and right subtrees. AVL trees are balanced when the balance factor is in the range of -1 to 1. When the balance factor becomes greater than 1 or less than -1, the tree is rebalanced. Here is an example of how to implement an AVL tree in Python:
class Node:
def __init__(self, data):
self.data = data
self.left = None
self.right = None
self.height = 1
class AVLTree:
def __init__(self):
self.root = None
def insert(self, data):
self.root = self._insert(self.root, data)
def _insert(self, node, data):
if node is None:
return Node(data)
if data < node.data:
node.left = self._insert(node.left, data)
else:
node.right = self._insert(node.right, data)
node.height = 1 + max(self.get_height(node.left), self.get_height(node.right))
balance = self.get_balance(node)
if balance > 1 and data < node.left.data:
return self.right_rotate(node)
if balance < -1 and data > node.right.data:
return self.left_rotate(node)
if balance > 1 and data > node.left.data:
node.left = self.left_rotate(node.left)
return self.right_rotate(node)
if balance < -1 and data < node.right.data:
node.right = self.right_rotate(node.right)
return self.left_rotate(node)
return node
And here is an example of how to implement an AVL tree in JavaScript:
class Node {
constructor(data) {
this.data = data;
this.left = null;
this.right = null;
this.height = 1;
}
}
class AVLTree {
constructor() {
this.root = null;
}
insert(data) {
this.root = this._insert(this.root, data);
}
_insert(node, data) {
if (node === null) {
return new Node(data);
}
if (data < node.data) {
node.left = this._insert(node.left, data);
} else {
node.right = this._insert(node.right, data);
}
node.height = 1 + Math.max(this.getHeight(node.left), this.getHeight(node.right));
const balance = this.getBalance(node);
if (balance > 1 && data < node.left.data) {
return this.rightRotate(node);
}
if (balance < -1 && data > node.right.data) {
return this.leftRotate(node);
}
if (balance > 1 && data > node.left.data) {
node.left = this.leftRotate(node.left);
return this.rightRotate(node);
}
if (balance < -1 && data < node.right.data) {
node.right = this.rightRotate(node.right);
return this.leftRotate(node);
}
return node;
}
}
And here is an example of how to implement an AVL tree in Java:
class Node {
int data;
Node left;
Node right;
int height;
public Node(int data) {
this.data = data;
left = null;
right = null;
height = 1;
}
}
class AVLTree {
Node root;
public AVLTree() {
root = null;
}
public void insert(int data) {
root = _insert(root, data);
}
private Node _insert(Node node, int data) {
if (node == null) {
return (new Node(data));
}
if (data < node.data) {
node.left = _insert(node.left, data);
} else {
node.right = _insert(node.right, data);
}
node.height = 1 + Math.max(getHeight(node.left), getHeight(node.right));
int balance = getBalance(node);
if (balance > 1 && data < node.left.data) {
return rightRotate(node);
}
if (balance < -1 && data > node.right.data) {
return leftRotate(node);
}
if (balance > 1 && data > node.left.data) {
node.left = leftRotate(node.left);
return rightRotate(node);
}
if (balance < -1 && data < node.right.data) {
node.right = rightRotate(node.right);
return leftRotate(node);
}
return node;
}
}
And here is an example of how to implement an AVL tree in Rust:
struct Node {
data: i32,
left: Option<Box<Node>>,
right: Option<Box<Node>>,
height: i32,
}
impl Node {
fn new(data: i32) -> Self {
Node {
data,
left: None,
right: None,
height: 1,
}
}
}
struct AVLTree {
root: Option<Box<Node>>,
}
impl AVLTree {
fn new() -> Self {
AVLTree { root: None }
}
fn insert(&mut self, data: i32) {
self.root = self._insert(self.root, data);
}
fn _insert(&mut self, node: Option<Box<Node>>, data: i32) -> Option<Box<Node>> {
match node {
None => Some(Box::new(Node::new(data))),
Some(mut current) => {
if data < current.data {
current.left = self._insert(current.left, data);
} else {
current.right = self._insert(current.right, data);
}
current.height = 1 + std::cmp::max(self.get_height(current.left.as_ref()), self.get_height(current.right.as_ref()));
let balance = self.get_balance(current.as_ref());
if balance > 1 && data < current.left.as_ref().unwrap().data {
return self.right_rotate(current);
}
if balance < -1 && data > current.right.as_ref().unwrap().data {
return self.left_rotate(current);
}
if balance > 1 && data > current.left.as_ref().unwrap().data {
current.left = self._insert(current.left, data);
return self.right_rotate(current);
}
if balance < -1 && data < current.right.as_ref().unwrap().data {
current.right = self._insert(current.right, data);
return self.left_rotate(current);
}
return Some(current);
}
}
}
}
It is important to note that the above code examples are not complete implementations of AVL trees, as they do not include the left and right rotate methods and the get_height and get_balance methods. These methods are important for maintaining the balance of the AVL tree, and should be implemented for a fully functional AVL tree. Additionally, these examples are provided for educational purposes only and shouldn’t be used in production as they are not optimized and may have performance issues.