• A binary search tree is a data structure that is designed for quick searching.

• It is a binary tree with a special relationship between each parent and its children as well as the descendants.

• It has a systematic way for data insertion and deletion in order to maintain itself as a binary search tree structure

  Put the new data at specific location, ถ้าเตี้ยกว่าไว้ซ้ายเอย สูงกว่าไว้ขวางี้! ก็ต้องเป็นงี้ไปตลอด

• Deletion ต้อง find Parent first

A Binary Search Tree (BST)— Basic Concepts

• A BST has the following properties
  • For each root, all elements of its left subtree must be less than or equal to the root
  • For each root, all elements of its right subtree must be greater than the root

Examples of BTs that are not BST

Same idea กับการหาคำศัพท์ใน Dictionary ที่เวลาเปิดหน้า Random มา แล้วถ้าคำศัพท์ที่ Alphabetically น้อยกว่า ก็ไปหน้าก่อนหน้า

BST Insertion

==ถ้า Insert Data ที่เท่ากันให้ใส่ไว้ฝั่งซ้าย!!!==

Insertion Steps

1. Find location of the parent of the node to be inserted (Compare ไปเรื่อย ๆ ตั้งแต่ Root จนกว่าจะเจอที่ที่เหมาะสมของ newData ที่เราจะ add เข้าไป)
2. Add the new node in an appropriate location of the parent found in step 1.

Example

• Insert 14 to a BST
  

#FinalExam ต้อง Compare ให้อาจารย์ดูด้วยนะ เดี๋ยวจะไม่ให้คะแนนอีก!!!!

• Insert 38 to a BST
  

BST Deletion

• ไม่ว่าจะเข้า Case ไหนก็ตามต้อง search for a node to be deleted and get its parent

Case 1: Delete Leaf Node

Case 2: Deleted Node Has 1 Child

2.1) Not The Root

• ก็เอา Parent/Root ข้ามไปจับกับตำแหน่งที่เหมาะสม
  

2.2) Is The Root

• ก็เอาตัวต่อมา (ลูกของมัน) เป็น Root เลย
  

Case 3: Deleted Node Has Both Left and Right Child

• Case 3 can also be done with minRight
• To avoid confusion, we will use only maxLeft throughout the course
  • In the lab we will implement only one method!

Find the largest element of the left subtree (maxLeft)

3.1) maxLeft has no child

• ให้ Replace data ตรง Node ที่จะลบด้วย maxLeft
  • แล้ว maxLeft ข้างล่างก็จะหายไปโดยการ set parent of maxLeft to have no child

3.2) maxLeft has left child

• ให้ Replace data ตรง Node ที่จะลบด้วย maxLeft
  • แล้วให้เอา maxLeft’s child ไปเป็นลูกของ maxLeft’s parent (Right)

3.3) maxLeft is a Left Child of Deleted Node

• ให้ Replace data ตรง Node ที่จะลบด้วย maxLeft
  • แล้วเอา left child ของ maxLeft เป็น left child ของ deleted node

Finding a largest element in a BST

• The largest element is always located in the right most location of the tree

Finding a smallest element in a BST

• The smallest element is always located in the left most location of the tree

Performance Analysis (Big-O)

• Which location in a BST takes the most time to search?
  • At the bottom-most
• Describe a BST of size n that achieves minimum height
  • Each level has maximum capacity
  • The binary tree with complete or nearly complete structure, ie. all levels are full, the last level is full or fully filled from left to right (no skip)
  • $\text{Max Height} = \lceil \log_2({n+1}) \rceil$ Refer to Height of a Binary Tree
• Describe a BST of size n that achieves maximum height
  • A tree that has exactly one node per level
• What are the BST’s maximum and minimum heights?
  • สมมติว่ามี $n$ nodes
  • Maximum: $n$ (At the bottom-most)
  • Minimum: $\lceil\log_2(n+1)\rceil$

Searching Performance in a BST

• Performance of the search operation $\propto$ the height of the tree.
• The worst case for a balanced BST of size n is $O(\log n)$
  • ก็มาจากสูตร minimum height นั่นแหละนะ
• The worst case for a unbalanced BST of size n is $O(n)$

Analysis of Operation (at worst case) of a BST of size $n$

• ก็ขึ้นอยู่กับ Height ทั้งหมด

BST Applications

• Improve databases for fast retrieval
• Sort the data
  • Apply in-order traversal to BST to get the sorted data from smallest to largest
  • Or repeatedly delete the smallest element