9.3 Binary Trees and Binary Search Trees

Binary trees are hierarchical data structures with nodes connected by edges. They're fundamental in computer science, offering efficient ways to organize and search data. This section explores various types of binary trees, their properties, and common operations performed on them.

Binary search trees (BSTs) are specialized binary trees that maintain a specific order of elements. They excel at searching, inserting, and deleting data efficiently. This section dives into BST operations, algorithms, and their performance characteristics, highlighting their strengths and limitations.

Binary Trees

Structure and Terminology of Binary Trees

Top images from around the web for Structure and Terminology of Binary Trees

• 

  IDisposable Thoughts - Data structures, Binary trees View original

  Is this image relevant?

• 

  Binary tree - Wikipedia View original

  Is this image relevant?

• 

  Binary tree - Wikipedia View original

  Is this image relevant?

• 

  IDisposable Thoughts - Data structures, Binary trees View original

  Is this image relevant?

• 

  Binary tree - Wikipedia View original

  Is this image relevant?

1 of 3

Top images from around the web for Structure and Terminology of Binary Trees

• 

  IDisposable Thoughts - Data structures, Binary trees View original

  Is this image relevant?

• 

  Binary tree - Wikipedia View original

  Is this image relevant?

• 

  Binary tree - Wikipedia View original

  Is this image relevant?

• 

  IDisposable Thoughts - Data structures, Binary trees View original

  Is this image relevant?

• 

  Binary tree - Wikipedia View original

  Is this image relevant?

1 of 3

• Binary tree consists of nodes connected by edges, forming a hierarchical structure
• Each node in a binary tree contains data and can have up to two children
• Left child branches to the left of its parent node, representing smaller or equal values
• Right child branches to the right of its parent node, representing larger values
• Root node serves as the topmost node in the tree, having no parent
• Leaf nodes are nodes without any children, located at the bottom of the tree
• Internal nodes have at least one child and are not leaf nodes

Properties and Types of Binary Trees

• Balanced tree maintains approximately equal height for all subtrees, optimizing search operations
• Full binary tree has every node with either zero or two children, maximizing node usage
• Complete binary tree fills all levels except possibly the last, which is filled from left to right
• Perfect binary tree has all internal nodes with exactly two children and all leaf nodes at the same level
• Degenerate tree resembles a linked list, with each node having only one child

Operations and Traversals in Binary Trees

• Preorder traversal visits the root, then the left subtree, and finally the right subtree
• Inorder traversal visits the left subtree, then the root, and finally the right subtree
• Postorder traversal visits the left subtree, then the right subtree, and finally the root
• Level-order traversal visits nodes level by level, from left to right
• Height of a binary tree measures the longest path from the root to a leaf node
• Depth of a node represents its distance from the root node

Binary Search Trees (BSTs)

Fundamentals and Properties of BSTs

• Binary search tree (BST) organizes data for efficient searching, insertion, and deletion
• BST property ensures all nodes in the left subtree have smaller values than the current node
• Right subtree of a BST contains nodes with larger values than the current node
• Inorder traversal of a BST produces a sorted list of elements
• BSTs support operations like search, insertion, and deletion with average time complexity of O(log n)

BST Operations and Algorithms

• Insertion in a BST compares the new value with nodes, moving left or right until finding the correct position
• Searching a BST starts at the root and moves left or right based on comparisons with node values
• Deletion in a BST involves three cases: deleting a leaf node, a node with one child, or a node with two children
• Successor of a node in a BST is the smallest value in its right subtree
• Predecessor of a node in a BST is the largest value in its left subtree

BST Performance and Limitations

• Best-case time complexity for BST operations occurs in balanced trees, achieving O(log n)
• Worst-case time complexity degrades to O(n) when the BST becomes unbalanced or skewed
• BST performance depends on the order of insertion and deletion of elements
• Skewed BSTs can form when inserting elements in sorted order, reducing efficiency
• Self-balancing BSTs address the issue of unbalanced trees by maintaining balance during operations

Self-Balancing BSTs

AVL Trees: Structure and Balancing

• AVL tree maintains balance by ensuring the height difference between left and right subtrees is at most 1
• Balance factor of a node in an AVL tree is the height of its right subtree minus the height of its left subtree
• AVL tree performs rotations to rebalance the tree after insertions or deletions
• Single rotation corrects imbalance when the insertion occurs in the outer grandchild of an unbalanced node
• Double rotation corrects imbalance when the insertion occurs in the inner grandchild of an unbalanced node

Red-Black Trees: Properties and Operations

• Red-black tree uses node coloring (red or black) and specific rules to maintain balance
• Every node in a red-black tree is either red or black
• Root node and null leaves (NIL) are always black
• Red nodes cannot have red children (red-red violation)
• Every path from the root to a leaf contains the same number of black nodes (black height property)
• Insertion in a red-black tree may require recoloring and rotations to maintain balance
• Deletion in a red-black tree involves more complex cases and may require multiple recoloring and rotations

Tree Rotations and Balancing Techniques

• Tree rotation alters the structure of a binary tree while preserving the binary search tree property
• Left rotation moves a node down and to the left, promoting its right child
• Right rotation moves a node down and to the right, promoting its left child
• Rotations help redistribute nodes to balance the tree and maintain optimal height
• AVL trees use rotations to correct imbalances immediately after insertions or deletions
• Red-black trees use rotations in combination with recoloring to maintain balance and tree properties