On average, a binary search tree will beat an array in the number of operations it takes to insert or delete an element. If you are inserting an element to the end of an array, all you have to do is put the data in the the first available memory address myArray[myArray.
However, if you have to insert at the beginning of an array, you will need to shift every element over. The same is true for deletion.
If the element is at the end like popping off a stack , then you simply change the stored length of the array. But if you delete the first element, all of the others will need to be shifted. Since the binary search tree does not require its elements to be stored in a contiguous block of memory, inserting or deleting a node can be done by simply adjusting some pointers.
Web Expand child menu Expand. Must Learn Expand child menu Expand. Big Data Expand child menu Expand. Live Project Expand child menu Expand. AI Expand child menu Expand. Toggle Menu Close. Program BST. We define a inner private class to define nodes in BST.
Each node contains a key, a value, a left link, a right link, and a node count. The left link points to a BST for items with smaller keys, and the right link points to a BST for items with larger keys.
The instance variable N gives the node count in the subtree rooted at the node. This field facilitates the implementation of various ordered symbol-table operations, as you will see. A recursive algorithm to search for a key in a BST follows immediately from the recursive structure: If the tree is empty, we have a search miss; if the search key is equal to the key at the root, we have a search hit.
Otherwise, we search recursively in the appropriate subtree. The recursive get method implements this algorithm directly. It takes a node root of a subtree as first argument and a key as second argument, starting with the root of the tree and the search key. Insert is not much more difficult to implement than search.
Indeed, a search for a key not in the tree ends at a null link, and all that we need to do is replace that link with a new node containing the key. The recursive put method accomplishes this task using logic similar to that we used for the recursive search: If the tree is empty, we return a new node containing the key and value; if the search key is less than the key at the root, we set the left link to the result of inserting the key into the left subtree; otherwise, we set the right link to the result of inserting the key into the right subtree.
The running times of algorithms on binary search trees depend on the shapes of the trees, which, in turn, depends on the order in which keys are inserted. It is reasonable, for many applications, to use the following simple model: We assume that the keys are uniformly random, or, equivalently, that they are inserted in random order.
The visualization below shows the result of inserting keys in a BST in random order. It displays the number of keys N , the maximum number of nodes on a path from the root to a leaf max , the average number of nodes on a path from the root to a leaf avg , the average number of nodes on a path from the root to a leaf in a perfectly balanced BST opt.
Your browser does not support the video tag. Order-based methods and deletion. An important reason that BSTs are widely used is that they allow us to keep the keys in order. As such, they can serve as the basis for implementing the numerous methods in our ordered symbol-table API.
Minimum and maximum. If the left link of the root is null, the smallest key in a BST is the key at the root; if the left link is not null, the smallest key in the BST is the smallest key in the subtree rooted at the node referenced by the left link. Admin AfterAcademy 11 Feb Share this blog and spread the knowledge. Share On Facebook. Share On Twitter. Share On LinkedIn. Share On Telegram.
Share On Reddit. Share On WhatsApp. Stay up to date.
0コメント