Table of Contents Definition Operations Rebalancing Definition An AVL tree is a binary search tree that is self-balancing based on the height of the tree. It manages this by adding a balance factor property to each node. Given a node \(X\), the balance factor is defined as:
\[ \text{BF}(X) = \text{Height}(\text{Left}(X)) - \text{Height}(\text{Right}(X)) \]
An binary tree is \textbf{left-heavy} when \(\text{BF}(X) < 0\) and \textbf{right-heavy} when \(\text{BF}(X) > 0\). An AVL tree is a binary search tree that is balanced if for every node \(X\), \(|\text{BF}(X)| \leq 1\).
Table of Contents What are Graphs? Graph Traversal Algorithms Breadth First Search Depth First Search What are Graphs? A graph is a data structure that is used to represent pairwise relationships between objects. Graphs are used in many applications, such as social networks, maps, and routing algorithms. These notes accompany the series of lectures on graphs for my Foundations of Computing course at the University of Texas - Arlington.
Table of Contents Definition Operations Exercises Red-Black Trees are modified Binary Search Trees that maintain a balanced structure in order to guarantee that operations like search, insert, and delete run in \(O(\log n)\) time.
Definition A red-black tree is a binary search tree with the following properties:
Every node is either red or black. The root is black. Every NULL leaf is black. If a node is red, then both its children are black. For each node, all simple paths from the node to descendant leaves contain the same number of black nodes. Figure 1: Red-Black Tree from CLRS Chapter 13.
Table of Contents Binary Search Trees Operations Analysis A $n$-ary tree is a graph-based data structure in which each node has up to \(n\) subnodes. It is supported by the following operations (not exclusive):
Search Insert Delete Tree-based data structures are defined by the following properties.
The size of a tree \(T\) is determined by the total number of nodes in \(T\). The root of a tree \(T\) is the starting point of \(T\). A leaf node of a tree \(T\) is a node that has no sub-nodes. The height of a tree is determined by the length of the shortest path between the root of \(T\) and the lowest leaf node of \(T\). If we limit the number of subnodes each node may have to 2, the structure becomes known as a binary tree. Limiting the structure in this way is of interest to us because of the efficiency benefits seen in operations applied to binary trees. If we narrow the scope of these trees further, we can define a binary search tree whose search operation, as the name might suggest, runs in \(\Theta(lg n)\) worst-case time.
Table of Contents Introduction to Data Structures Review: Pointers Arrays Matrices Multi-Dimensional Arrays Stacks Queues Introduction to Data Structures Data structures are fundamental concepts in computer science that allow us to organize and store data in a way that enables efficient access and modification. They are essential building blocks for creating efficient and sophisticated computer programs and databases. Different types of data structures include arrays, linked lists, stacks, queues, trees, graphs, and many more, each serving a specific purpose and suited to specific applications.
Table of Contents Singly-Linked Lists Doubly-Linked Lists Operations Exercises A linked list is a dynamic and aggregate data structure made up of a collection of nodes. The nodes of a linked list can store any data type and are not enforced to contain the same data type. A basic node structure may be defined as
struct node { void *data; struct node *next; }; Singly-Linked Lists A singly-linked list, the most basic form, has a reference to the first node in the list, called the head, and a single link between each node.