Binary Search Trees, or BSTs for short, are a type of binary tree which follows a certain ordering property.
In Binary Search Trees(BSTs), the left child of a node contains a lesser value than the node itself, while the right node contains a greater value than the node itself. This ordering property allows efficient searching, insertion, and deletion operations.
Searching in a binary search tree involves comparing the targeted value with the values in each node and travesing the tree. This operation can be used recursively or iteratively.
Now we have insertion and deletion. These two are important operations in binary search trees so that these operations could add and remove nodes while maintaining the BST property. In Insertion, to insert a new node into a BST, we begin from the root and go down the tree, or to put it in a better term, traverse down the tree, until an appropriate position for the node has been found. If the new node's value is lesser than the current nodem we go to the left child, else, we go to the right child. When we reach a null child, we create a new node with the desire value and attach it to the approriate child pointer. Now in deletion, To delete a node from a BST, it requires handling these three cases. One case is that if the node to be deleted is a leaf node, we just simply remove the node from the tree. The other case is if the node to be deleted has one child, we just replace the node with its child. The last case is if the node to be deleted has two children, we find the inorder predecessor or successor and replace the node with it, and delete the predecessor or successor node.
Binary Search Trees can sometimes become unbalanced, which can lead to inefficient search and traversal operations. Tree balancing techniques aim to maintain a balanced structure in binary search trees to ensure optimal performance. AVL Trees and Red-Black trees are the two commonly used self-balancing binary search trees. In AVL Trees, they are self-balancing binary search trees in which the heights of the left and right subtrees differ by at most one. In order to maintain balance, they perform rotations and restructure the tree after inserting and deleting nodes. This ensures the height of the tree to be logarithmic, resulting in efficient operations. In Red-Black Trees, they are another type of self-balancing binary search trees where they guarantee that the tree is approximatelt balanced by assigning colors, either red or black, to each node and applying specific rules during insertions and deletions. These trees provide efficient operations with a maximum height of 2 * log(n+1), where n is the number of nodes.
BSTs have many use cases and applications like efficient searching, range queries, implementing associative arrays, database indexing and auto-complete functionality. These operations play a crucial role in efficient data retrieval, insertion, and deletion.
In a binary tree, each node can have two children at most. The two children are referred to as left and right child. Binary Trees are used in various applications and algorithms due to how simple and efficient they are.
Traversal refers to visiting each node in a tree in a specific order. The three common used binary tree traversal algorithms are Inorder, Preorder, and Postorder Traversal. In inorder traversal, the left subtree is traversed first, and then we head to the current node, and then we traverse to the right tree. In preorder traversal, the current node is visited first, followed by traversing the left subtree and then the right subtree. In postorder traversal, we traverse first to the left subtree, following the right subtree, and the we finally visit the current node.
There are Binary Tree Operations, which are insertion, deletion and searching. The terminoligies and properties used in Binary Trees are Root, Parent, Left Child, Right Child, Leaf, Internal Node, Height, and Depth. Overall, Binary Trees are fundemental datastructures that allow efficient organization and retrieval of data.
Posted using Honouree
