Data Structures and Algorithms in Swift: Implement Stacks, Queues, Dictionaries, and Lists in Your Apps

© Elshad Karimov 2020

E. KarimovData Structures and Algorithms in Swifthttps://doi.org/10.1007/978-1-4842-5769-2_11

11. Binary Search Tree

Elshad Karimov¹ 

(1)

New York, New York, USA

 

A Binary Search Tree (BST) is a binary tree in which each node has at most two children, and it facilitates fast search, insertion, and deletion operations. The time complexity of each operation is O(log n), which is considerably faster than linear search. The two main characteristics of the Binary Search Trees are as follows:

• The value of the left node must be lesser than the value of its parent.

• The value of the right node must be greater than or equal to the value of its parent.

Figure 11-1 shows the basic structure of the Binary Search Tree.

Figure 11-1

Basic structure ...