trees.md

Trees

Table of contents

• Binary trees
  • Binary search trees
  • Self-balancing binary search trees
    • AVL (Adelson-Velskiĭ–Landis) trees
  • Other binary trees
    • Binary indexed trees (Fenwick trees)
• B-trees
  • 2-3 trees
• Traversal
• Volumetric trees
  • OpenVDB

---

Binary trees

A binary tree is a tree in which no node can have more than two children.

📝

• The total number of binary trees with N different keys is given by N! C(N), where C(N) is the N^th Catalan number. Asymptotically C(N) ∼ 4N / [N3/2 sqrt π].
• The average height of a randomly built binary search tree is O(log n).

Binary search trees

A binary search tree is a binary tree that satisfies the binary search property: the key in each node must be greater than or equal to any key stored in the left subtree, and less than or equal to any key stored in the right subtree.

📝

• The total number of binary search trees with N different keys is given by the N^th Catalan number C(N). Asymptotically C(N) ∼ 4N / [N3/2 sqrt π].

🎥

• Binary search trees – MIT OCW 6.006: Introduction to algorithms (2011)

📖

• Sec. 2.3.1: Binary search trees, Sec: Selection sort – E.Horowitz, S.Sahni, S.Rajasekaran. Computer algorithms – W.H.Freeman (1997)

Self-balancing binary search trees

A self-balancing binary search tree is a binary search tree that automatically keeps its height small during arbitrary insertions and deletions.

📝

• For a self-balancing binary search tree containing N nodes, lookup, insertion, and removal of an item takes O(log N) worst-case time, and ordered enumeration of all nodes takes O(N) time.
• Self-balancing binary search trees can be used to implement sorted associative containers. For example, std::set and std::map are typically implemented using red-black trees.
• Self-balancing binary search can be used to count the number of inversions in an array and the number of smaller/larger elements on the right/left side of each element in an array.

🔗

• Self-balancing binary search tree – Wikipedia

AVL (Adelson-Velskiĭ–Landis) trees

An AVL tree is a self-balancing binary search tree in which for every node the height of the left and right subtrees can differ by at most one.

📝

• The height of an AVL tree with N nodes lies between log2(N + 1) and 1.4404 log2(N + 2) - 0.3277.
• For insertions, one rotation always suffices. For deletions, O(log N) rotations may be required. Non-recursive insertions and deletions are generally faster, but harded to code and read.
• Double rotations can be made more efficient if performed as a single step and not as two single rotations.
• Balance factors, i.e. differences in heights, can be stored instead of heights. This results in faster but more complicated code. If a balance factor is stored as a separate data member, there is no profit in the amount of space used due to data alignment.
• AVL trees require at most 45% more comparisons than optimal binary search trees.

🔗

• AVL tree – Wikipedia
• C++ AVL tree template
• AVL trees: Tutorial and C++ implementation
• Simple AVL tree in C++
• AVL tree implementation in C++

📖

• Sec. 6.2.3: Balanced trees – D.E.Knuth. The art of computer programming. Vol. 3: Sorting and searching (1998)
• Sec. 4.4: AVL trees – M.A.Weiss. Data structures and algorithm analysis in C++ (2014)
• Sec. 4.3.4: AVL trees – U.Manber. Introduction to algorithms: A creative approach (1989)

📄

• G.M.Adelson-Velskiĭ, E.M.Landis. An algorithm for organization of information. In english, In russian – Doklady Akademii Nauk SSSR 146, 263 (1962)

🎥

• AVL trees, AVL sort – MIT OCW 6.006: Introduction to algorithms (2011)

💫 Visualizations

• AVL tree visualization

Other binary trees

Binary indexed trees (Fenwick trees)

A binary indexed tree is a data structure that can efficiently update elements and calculate prefix sums.

📝

• Both 0-based and 1-based indexing can be used in equally elegant ways.
• A Fenwick tree can be built for any cancellative semigroup (e.g. for the set of integers under addition or multiplication); if the cancellation property doesn't hold (e.g. for min(•, •)), a segment tree can be used.
• Applications: arithmetic coding, Monte-Carlo simulations

🔗

• Fenwick tree – Wikipedia
• Binary indexed trees – Topcoder
• Fenwick tree – Brilliant
• A JavaScript implementation of binary indexed tree – Microsoft @ GitHub
• What are the advantage of binary indexed tree (BIT or Fenwick tree) over segment tree? – Quora

🎥

• Fenwick trees – Algorithms Live!
• W.Fiset. Fenwick tree/Binary indexed tree

📖

• Sec. 2.4.4: Binary indexed (Fenwick) tree – S.Halim, F.Halim. Competitive programming (2013)

📄

• P.M.Fenwick. A new data structure for cumulative frequency tables – Software: Practice and Experience 24, 327 (1994)

---

B-trees

🎥

• 2-3 Trees and B-Trees – MIT OCW 6.046J: Design and analysis of algorithms (2015)

📖

• Ch. 18: B-trees – T.H.Cormen, C.E.Leiserson, R.L.Rivest, C.Stein. Introduction to algorithms (2009)

2-3 trees

---

Traversal

See also: Graphs – Traversal

🔗

• Tree traversal – Wikipedia

---

Volumetric trees

OpenVDB

🔗

• OpenVDB
• K.Museth. OpenVDB: An open source data structure and toolkit for high-resolution volumes – BIDS (2015)