This is the fifth day of my participation in Gwen Challenge
Today we are going to look at binary search trees
Binary Search Tree
The most important feature of binary search tree is that it supports fast insertion, deletion and search of dynamic data set. Binary lookup trees also support fast lookup of maximum and minimum nodes, precursor and successor nodes.
Given that we have such efficient hash tables, can we replace them with hash tables everywhere we use binary trees? Is there anything you can’t do with a hash table that you have to do with a binary tree?
A binary search tree requires that at any node in the tree, the value of each node in the left subtree is less than the value of this node, and the value of each node in the right subtree is greater than the value of this node.
Middle order traversal search binary tree, can output ordered data sequence, time complexity is O(n){O(n)}O(n), very efficient. So a binary search tree is also called a binary sort tree.
Binary search tree that supports repeated data
The range of L is log base 2 of n plus 1, log base 2 of n plus 1. The number of levels of a complete binary tree is less than or equal to log2n +1, that is, the height of a complete binary tree is less than or equal to log2n.
In binary search trees, the time complexity of search, insert, delete and many other operations is proportional to the height of the tree. The time complexity of the two extreme cases is O(n) and O(logn) respectively, corresponding to the case where the binary tree degenerates into a linked list and the complete binary tree respectively.
The height of balanced binary search tree is close to logn, so the time complexity of insert, delete and search operation is stable, which is O(logn).
First, the data in the hash table is stored unordered, so if you want to output ordered data, you need to sort it first. For binary search trees, we only need middle-order traversal to output ordered data sequences within O(n) time complexity.
Second, it takes a lot of time to expand hash table, and the performance is not stable when hash conflicts are encountered. Although the performance of binary lookup tree is not stable, in engineering, the performance of the most commonly used balanced binary lookup tree is very stable, and the time complexity is stable at O(logn).
Third, in general terms, although the time complexity of operations such as the hash table lookup is constant, the constant is not necessarily less than logn because of hash conflicts, so the actual lookup may not be faster than O(logn). Plus the time consuming of the hash function, it is not necessarily more efficient than balancing binary search trees.
Fourth, the construction of hash tables is more complex than binary search trees, and there are many things to consider. Such as the design of hash functions, conflict resolution, capacity expansion, capacity reduction, etc. Balanced binary search tree only needs to consider the problem of balance, and the solution of this problem is relatively mature and fixed. Finally, in order to avoid too many hash collisions, the hash table load factor should not be too large, especially if the hash table is based on the open addressing method, otherwise some storage space will be wasted.
How do you programmatically find the exact height of a given binary tree? Leetcode 104 leetcode 450
Recursive method, root node height = Max (left subtree height, right subtree height)+1 The second method can be hierarchical traversal, each layer records the length of the current queue, this is the queue end, each layer queue head starting from 0. Each element is then iterated with the header subscript +1. Until the team head index equals the team tail index. This indicates that the current layer traversal is complete. At the beginning of each layer, the height of the tree is +1. And when the queue is empty, you get the height of the tree.