All geek questions in one place

Duplicate entries in binary search tree

I have a very simple question regarding BST. I have seen several BST definitions regarding duplicate entries. Some define BST as not allowing duplicate entries, others that the node the left child is <= for the value of the nodes, and the right child is greater than the value of the node, and some definitions are the opposite (the left child is lt than node, the right child → =).

So my question is, what is the official definition (if one exists) for the BST in relation to duplicate entries? For example, what would a BST look like after pasting in: 3, 5, 10, 8, 5, 10?

Thanks in advance for clarifying the definition and answering my question!

+4
source share
2 answers

One of the well-known books in the field of algorithm and data structure is the publication of CLRS , also known as the bible of data structures and algorithms:

enter image description here

According to the definition of this book, duplicate entries are placed in the tree to the right of the node that contains the same key. As an example, consider the BST insertion algorithm adopted in this book:

enter image description here

+6
source

The important thing is that not having duplicates in the tree provides a quick search time. If you have duplicates on one side of the node, your search time will suffer because you need to go through all the duplicates before continuing.

http://en.wikipedia.org/wiki/Binary_search_tree

+3
source

Source: https://habr.com/ru/post/1388967/

More articles:


All Articles