Algorithms
  • Introduction
  • Analysis of Algorithms
  • Numbers
    • Reverse Integer
    • Palindroms
      • Valid Palindrome
    • Prime factor
    • Prime Number
    • Roman to Integer
    • Happy Number
    • p^k
  • Searching
    • Union-Find Algorithms
    • Finding Peak
    • Find Sum in Array
    • Binary Search
      • Find Index Binary Search
      • Sqrt(x)
      • Search in Rotated Sorted Array
      • Guess Number Higher or Lower
      • First Bad Version
      • Find Peak Element
      • Find Minimum in Rotated Sorted Array
      • Find Minimum in Rotated Sorted Array II
      • Search for a Range
      • Closest Binary Search Tree Value
      • Find K Closest Elements
      • Search in a Sorted Array of Unknown Size
      • Pow(x, n)
      • Valid Perfect Square
      • Find Minimum in Rotated Sorted Array II
      • Intersection of Two Arrays
      • Intersection of Two Arrays II
      • Two Sum II - Input array is sorted
      • Find the Duplicate Number
    • Longest Common Prefix
  • Sorting
    • Elementary Sorts
    • Insertion Sort
    • Bubble Sort
    • Mergesort
    • Quicksort
    • Radix Sort
    • Heap Sort
  • Data Structures
    • Array & List
      • Find Pivot Index
      • Largest Number At Least Twice of Others
      • Plus One
      • Diagonal Traverse
      • Spiral Matrix
      • Pascal's Triangle
      • Implement strStr()
      • Add Binary
      • Duplicate Counts
      • Find Duplicates
      • Reverse String
      • Array Partition I
      • Two Sum II - Input array is sorted
      • Remove Element
      • Max Consecutive Ones
      • Minimum Size Subarray Sum
      • Reverse Words in a String
      • Reverse Words in a String III
      • Remove Duplicates from Sorted Array
      • Move Zeroes
      • Rotate Array
      • Rotate Image
      • Best Time to Buy and Sell Stock
      • Best Time to Buy and Sell Stock II
      • Valid Anagram
      • 3Sum
      • String to Integer (atoi)
      • Count and Say
      • Merge Sorted Array
      • Shuffle an Array
      • Max Area of Island
    • Matrix
    • Stack
      • Valid Parentheses
      • Min Stack
    • Queue
    • Linked List
      • Design Linked List
      • Design Doubly Linked List
      • Find Middle Element
      • Doubly Linked List
      • Cyclic Linked List
      • Linked List Cycle II
      • Find Nth Element from End
      • Remove Nth Node From End of List
      • Add Two Numbers
      • Merge Two Sorted Lists
      • Remove Nth Node From End of List
      • Reverse Linked List
      • Remove Linked List Elements
      • Odd Even Linked List
      • Design Doubly Linked List
      • Flatten a Multilevel Doubly Linked List
      • Rotate List
      • Copy List with Random Pointer
      • Insert into a Cyclic Sorted List
      • Delete Node in a Linked List
      • Palindrome Linked List
    • Set
      • Intersection of Two Arrays
      • Single Number
      • Contains Duplicate
      • Contains Duplicate II
      • Jewels and Stones
      • Longest Substring Without Repeating Characters
      • Two Sum III - Data structure design
      • Valid Sudoku
      • Missing Number
    • Map
      • Two Sum
      • Isomorphic Strings
      • Minimum Index Sum of Two Lists
      • First Unique Character in a String
      • Intersection of Two Arrays II
      • Logger Rate Limiter
      • Group Anagrams
      • Group Shifted Strings
      • Find Duplicate Subtrees
      • 4Sum II
      • Top K Frequent Elements
      • Unique Word Abbreviation
      • Insert Delete GetRandom O(1)
    • Binary Tree
      • Binary Tree Preorder Traversal
      • Binary Tree Inorder Traversal
      • Binary Tree Postorder Traversal
      • Binary Tree Level Order Traversal
      • Maximum Depth of Binary Tree
      • Symmetric Tree
      • Path Sum
      • Balanced Binary Tree
      • Count Univalue Subtrees
      • Construct Binary Tree from Inorder and Postorder Traversal
      • Construct Binary Tree from Preorder and Inorder Traversal
      • Populating Next Right Pointers in Each Node
      • Lowest Common Ancestor of a Binary Tree
      • Serialize and Deserialize Binary Tree
      • Median of Two Sorted Arrays
      • Invert Binary Tree
      • Find K-th Smallest Pair Distance
      • Split Array Largest Sum
    • Heap
    • Binary Search Tree
      • Validate Binary Search Tree
      • Inorder Successor in BST
      • Binary Search Tree Iterator
      • Search in a Binary Search Tree
      • Insert into a Binary Search Tree
      • Delete Node in a BST
      • Kth Largest Element in a Stream
      • Lowest Common Ancestor of a Binary Search Tree
      • Contains Duplicate III
      • Height-Balanced BST
        • Balanced Binary Tree
        • Convert Sorted Array to Binary Search Tree
    • Map
    • N-ary Tree
      • N-ary Tree Preorder Traversal
      • N-ary Tree Postorder Traversal
      • N-ary Tree Level Order Traversal
      • Maximum Depth of N-ary Tree
      • Encode N-ary Tree to Binary Tree
      • Serialize and Deserialize N-ary Tree
    • Trie
      • Implement Trie (Prefix Tree)
      • Map Sum Pairs
      • Replace Words
      • Design Search Autocomplete System
      • Maximum XOR of Two Numbers in an Array
      • Add and Search Word - Data structure design
      • Word Search II
      • Word Squares
      • Longest Common Prefix
      • Palindrome Pairs
    • Balanced Tree
      • B-Tree
      • Red-black Tree
      • AVL Tree
    • Graph
      • A* Search
      • Breadth First Search
      • Depth First Search
      • Dijkstra Algorithm
  • Sequences
    • Fibonacci Sequence
  • Dynamic Programming
    • Knapsack problem
    • Climbing Stairs
    • Best Time to Buy and Sell Stock
    • Maximum Subarray
    • House Robber
  • Interviews
    • Google Leetcode
      • Repeated String Match
      • K Empty Slots
      • Next Closest Time
      • Longest Univalue Path
      • License Key Formatting
      • Spiral Matrix
      • Plus One
      • Trapping Rain Water
      • Longest Substring with At Most K Distinct Characters
      • Add Bold Tag in String
      • Game of Life
      • Read N Characters Given Read4
      • Read N Characters Given Read4 II - Call multiple times
      • One Edit Distance
      • Valid Palindrome
      • Valid Number
      • Valid Parentheses
      • Image Smoother
      • Intersection of Two Arrays
      • Max Consecutive Ones
      • Max Consecutive Ones II
      • Shortest Palindrome
      • First Missing Positive
      • First Unique Character in a String
      • Move Zeroes
      • Remove Duplicates from Sorted Array
      • Merge k Sorted Lists
      • Insert into a Cyclic Sorted List
      • Evaluate Division
      • Inorder Successor in BST
      • Robot Room Cleaner
      • Redundant Connection II
      • Course Schedule
      • Validate Binary Search Tree
      • Closest Binary Search Tree Value
      • Word Squares
      • Strobogrammatic Number II
      • Word Search II
      • Android Unlock Patterns
      • Minimum Window Substring
      • Kth Largest Element in an Array
      • Shortest Distance from All Buildings
      • Find K-th Smallest Pair Distance
      • Find K Pairs with Smallest Sums
      • Range Module
      • Insert Interval
      • Sort Transformed Array
      • Merge Intervals
      • Longest Palindromic Substring
      • Next Greater Element I
      • Pacific Atlantic Water Flow
      • Evaluate Reverse Polish Notation
      • Decode Ways
      • Word Break
      • Sentence Screen Fitting
      • Maximum Vacation Days
      • Edit Distance
      • Minimum Path Sum
      • House Robber II
      • Moving Average from Data Stream
      • Peeking Iterator
      • Binary Search Tree Iterator
      • Zigzag Iterator
      • Design Tic-Tac-Toe
      • Range Sum Query 2D - Mutable
      • UTF-8 Validation
      • Maximum Product of Word Lengths
  • Other
    • Game of Life
Powered by GitBook
On this page
  • What is a Height-Balanced BST?
  • Why Using a Height-Balanced BST?
  • How to Implement a Height-Balanced BST?
  • Practical Application of the Height-balanced BST
  • Conclusion

Was this helpful?

  1. Data Structures
  2. Binary Search Tree

Height-Balanced BST

PreviousContains Duplicate IIINextBalanced Binary Tree

Last updated 5 years ago

Was this helpful?

In this article, we are going to help you understand the general concept of a balanced BST.

What is a Height-Balanced BST?

Terminology used in trees:

  • Depth of node - the number of edges from the tree's root node to the node

  • Height of node - the number of edges on the longest path between that node and a leaf

  • Height of Tree - the height of its root node

Aheight-balanced(orself-balancing) binary search tree is a binary search tree that automatically keeps its height small in the face of arbitrary item insertions and deletions. That is, the height of a balanced BST withN nodes is alwayslogN. Also, the height of the two subtrees of every node never differs by more than 1.

WhylogN?

  • A binary tree with height

    h

    contains at most

    .

  • In other word, a binary tree with

    N

    nodes and height

    h

    :

    .

  • That is:

    .

Here is an example of a normal BST and a height-balanced BST:

As we mentioned before, the height of a balanced BST withN nodes is alwayslogN. We can calculate the total number of nodes and the height of the tree to determine if this BST is a height-balanced BST.

Also, in the definition, we mentioned a property of height-balanced BST: the depth of the two subtrees of every node never differ by more than 1. We can also validate the tree recursively according to this rule.

Why Using a Height-Balanced BST?

We have introduced binary search tree and related operations, including search, insertion and deletion in the previous article. When we analyze the time complexity of these operations, it is worth noting that the height of the tree is the most important factor. Taking search operation as an example, if the height of the BST is h, the time complexity will beO(h). The height of the BST really matters.

Therefore, the height of a BST withN nodes can vary fromlogN toN. That is, the time complexity of search operation can vary fromlogN toN. It is a huge difference in the performance.

Therefore, a height-balanced BST play an important role in improving the performance.

How to Implement a Height-Balanced BST?

There are several different implementations for height-balanced BSTs. The details of these implementations are different but they have similar goals:

  1. The data structure should satisfy the binary search property and the height-balanced property.

  2. The data structure should support the basic operations of BST, including search, insertion and deletion within

    O(

    logN

    )

    time even in worst case.

We provide a list of popular height-balanced BSTs for your reference:

We are not going to talk about the details of these implementations in this article series.

Practical Application of the Height-balanced BST

The height-balanced BST is widely used in practice since it can provide search, insertion and deletion operations all inO(logN)time complexity.

The most profound use is in set/map. The principle of set and map are similar. We will focus on the set in the following discussion.

Set is another data structure which can store a lot of keys without any particular order or any duplicate elements. The basic operations it should support are to insert new elements into the set and to check if an element is in the set or not.

Typically, there are two kinds of sets which are widely used:hash setandtree set.

Thetree set,TreeSetin Java orsetin C++, is implemented by the height-balanced BST. Therefore, the time complexity of search, insertion and deletion are allO(logN).

Thehash set,HashSetin Java orunordered_setin C++, is implemented by hash, but the height-balanced BST also plays an important role in hash set. When there are too many elements with the same hash key, it will cost O(N)time complexity to look up for a specific element, whereNis the number of elements with the same hash key. Typically, the height-balanced BST will be used here to improve the performance fromO(N)toO(logN).

The essential difference between the hash set and the tree set is that keys in the tree set areordered.

Conclusion

A height-balanced BST is a special form of BST which aims at improving the performance. The details of implementations are outside the scope of this article series and are not required in most interviews. But it is useful to understand the general idea of a height-balanced BST and how height-balanced BSTs can help you in your algorithm designs.

Using the definition, we can determine if a BST is height-balanced ().

So let's discuss the relationship between the number of nodesN and the height of the treeh. For a height-balanced BST, as we discussed in the previous section,. But for a normal BST, in the worst case, it can degenerate into a chain.

Balanced Binary Tree
Red-black tree
AVL tree
Splay tree
Treap