Outline

• Trees
  • Binary Search Tree
    • Search and Insertion
    • Delete
    • BST over Hash Table
    • Construction and Conversions
    • Check Smallest/Largest Element

Outline

• Trees
  • Red Black Tree and Threaded Binary Tree
  • AVL Trees
  • B Trees
    • Defitinion of B Trees
    • Basic operations on B tree
    • Deleting a key from a B tree
  • 2 3 4 Trees
  • 2 3 Trees
  • B+ Trees

Outline

• Trees
  • R Trees
  • Red - Black Tree Datastructure
  • Splay Tree Datastructure
  • Augmenting Data Structures
    • Dynamic order statistics
    • How to augment a data structure

Outline

• Trees

  • Interval trees
  • van Emde Boas Trees
    • Preliminary approaches
    • A recursive structure
    • The van Emde Boas tree
  • Binomial Trees
  • Comparison of Search Trees
  • Minimax Tree

Binary Search Tree

• http://www.btechsmartclass.com/data_structures/binary-search-tree.html

• https://visualgo.net/en/bst?slide=1 (Select BINARY SEARCH TREE)

• https://www.cs.usfca.edu/~galles/visualization/BST.html

• Search and Insertion

• Delete

BST over Hash Table

• https://www.geeksforgeeks.org/advantages-of-bst-over-hash-table/?ref=lbp

• Construction and Conversions

• Check Smallest/Largest Element

Red Black Tree and Threaded Binary Tree

• https://www.geeksforgeeks.org/threaded-binary-tree/

AVL Trees

• http://www.btechsmartclass.com/data_structures/avl-trees.html
• https://visualgo.net/en/bst (Select AVL)
• https://www.cs.usfca.edu/~galles/visualization/AVLtree.html

B Trees

• http://www.btechsmartclass.com/data_structures/b-trees.html
• https://www.cs.usfca.edu/~galles/visualization/BTree.html

Defitinion of B Trees

• https://www.geeksforgeeks.org/introduction-of-b-tree-2/

Basic operations on B tree

• https://www.geeksforgeeks.org/insert-operation-in-b-tree/
• https://www.guru99.com/b-tree-example.html

Deleting a key from a B tree

• https://www.geeksforgeeks.org/delete-operation-in-b-tree/

2 3 4 Trees

• https://en.wikipedia.org/wiki/2–3–4_tree

2 3 Trees

• https://en.wikipedia.org/wiki/2–3_tree

B+ Trees

• https://www.geeksforgeeks.org/introduction-of-b-tree/
• https://www.cs.usfca.edu/~galles/visualization/BPlusTree.html
• https://www.geeksforgeeks.org/difference-between-b-tree-and-b-tree/?ref=rp

R Trees

• https://www.geeksforgeeks.org/introduction-to-r-tree/?ref=rp

Red - Black Tree Datastructure

• http://www.btechsmartclass.com/data_structures/red-black-trees.html
• https://www.geeksforgeeks.org/red-black-tree-set-1-introduction-2/?ref=rp
• https://www.geeksforgeeks.org/red-black-tree-set-2-insert/
• https://www.geeksforgeeks.org/red-black-tree-set-3-delete-2/

Splay Tree Datastructure

• http://www.btechsmartclass.com/data_structures/splay-trees.html
• https://www.geeksforgeeks.org/splay-tree-set-1-insert/?ref=rp
• https://www.geeksforgeeks.org/splay-tree-set-2-insert-delete/
• https://www.geeksforgeeks.org/splay-tree-set-3-delete/?ref=rp

Augmenting Data Structures

• http://cs.bilkent.edu.tr/~ugur/teaching/cs502/material/cs502_2_ADS.pdf

• https://iq.opengenus.org/augmented-data-structures/

• http://staff.ustc.edu.cn/~csli/graduate/algorithms/book6/chap15.htm

• http://www.facweb.iitkgp.ac.in/~sourav/Lecture-11.pdf

Dynamic order statistics

• http://www.facweb.iitkgp.ac.in/~sourav/Lecture-11.pdf

How to augment a data structure

• http://www.facweb.iitkgp.ac.in/~sourav/Lecture-11.pdf

Interval trees

• https://www.geeksforgeeks.org/interval-tree/

van Emde Boas Trees

• https://www.geeksforgeeks.org/van-emde-boas-tree-set-1-basics-and-construction/

• https://web.stanford.edu/class/archive/cs/cs166/cs166.1146/lectures/14/Small14.pdf

• Preliminary approaches

• A recursive structure

Binomial Trees

• https://www.geeksforgeeks.org/binomial-heap-2/#:~:text=What is a Binomial Tree,as leftmost child or other.

Comparison of Search Trees

• http://www.btechsmartclass.com/data_structures/comparison-of-search-trees.html

Minimax Tree

• https://www.geeksforgeeks.org/minimax-algorithm-in-game-theory-set-1-introduction/