Trees

A tree is a hierarchical data structure composed of nodes connected by edges. The structure starts with a single root node and extends downwards, forming parent-child relationships among nodes. Each node, except the root, has exactly one parent, and nodes with no children are called leaf nodes. Various concepts and properties characterize trees.

Concepts

Nodes and Edges

• Node: Basic unit in a tree that contains data and may have zero or more child nodes.
• Edge: Connection between nodes that represents relationships.

Root, Parent, Child, and Leaf

• Root Node: The topmost node in a tree, without a parent.
• Parent Node: A node that has one or more child nodes.
• Child Node: A node connected to another node, known as its parent.
• Leaf Node: A node without children.

Subtrees and Paths

• Subtree: Any node in a tree can be considered the root of a subtree.
• Path: The sequence of nodes connected by edges from the root to a specific node.

Ascendants and Descendants

• Ascendants: Nodes on the path from the root to a specific node.
• Descendants: Nodes reachable from a specific node by following edges.

Height and Depth

• Height of a Node: Maximum path length from the node to a leaf.
• Depth of a Node: Path length from the root to the node.

Degree

• Degree of a Node: Number of children a node has.

Ascendants and Descendants

Ascendents of node 12:

• 50, 90, 75.

Descendants of node 90:

• 50, 37, 12.

Height and depth

Binary Trees

A binary tree is a specific type of tree where each node has at most two children: a left child and a right child.

Full and Perfect Binary Trees

Full Binary Tree: Every node is a leaf or has exactly two children.

• It has n + 1 leaves, where n is the number of internal nodes.

Perfect Binary Tree: A full binary tree where all leaves have the same depth.

• It has 2^(h + 1) - 1 nodes, where h is the height.

Tree Traversals

Tree traversals are methods for visiting and exploring all nodes in a tree.

Types of Traversals:

• In-Order: Visit left subtree, visit the root, visit right subtree.
• Pre-Order: Visit the root, visit the left subtree, visit the right subtree.
• Post-Order: Visit left subtree, visit right subtree, visit the root.
• Level-Order: Visit nodes level by level, starting from the root and moving left to right across each level.

Binary Search Tree (BST)

A Binary Search Tree is a binary tree with the property that for each node, all nodes in its left subtree have values less than the node, and all nodes in its right subtree have values greater than the node.

Operations on BST

• Search: Locate a node with a given key efficiently.
• Insertion: Add a new node while maintaining the BST property.
• Deletion: Remove a node while preserving the BST property.
• Performance: Search, insertion, deletion have an average time complexity of O(log n).

AVL Tree or Balanced Trees

AVL trees are a type of self-balancing binary search tree where the height difference between the left and right subtrees (balance factor) of any node is at most 1.

AVL Tree Operations

• Balance Factor: The height difference between the left and right subtrees.
• Balancing the Tree: Ensuring the balance factor is maintained.
• Rotation: Simple and double rotations to maintain balance.
• Insertion: Rebalance the tree after insertion to maintain AVL property.
• Deletion: Rebalance the tree after deletion to maintain AVL property.
• BST vs AVL Tree: Comparison of binary search trees and AVL trees.
• Sorting in AVL Tree: Utilizing the in-order traversal for sorted order.

Kd-trees

A Kd-tree, or k-dimensional tree, is a binary tree used for multidimensional searches, such as nearest neighbor or range searches.

2d-tree

A 2d-tree is a specific instance of a Kd-tree where k is 2, representing points in a 2-dimensional space.