二进制搜索树

A tree is a data structure composed of nodes that has the following characteristics:

树是由具有以下特征的节点组成的数据结构：

1. Each tree has a root node (at the top) having some value.
   每棵树都有一个具有某些值的根节点(在顶部)。
2. The root node has zero or more child nodes.
   根节点具有零个或多个子节点。
3. Each child node has zero or more child nodes, and so on. This create a subtree in the tree. Every node has it’s own subtree made up of his children and their children, etc. This means that every node on its own can be a tree.
   每个子节点都有零个或多个子节点，依此类推。 这将在树中创建一个子树。 每个节点都有自己的子树，该子树由其子代及其子代组成。这意味着每个节点自身都可以是一棵树。

A binary search tree (BST) adds these two characteristics:

二进制搜索树(BST)添加了以下两个特征：

1. Each node has a maximum of up to two children.
   每个节点最多有两个子节点。
2. For each node, the values of its left descendent nodes are less than that of the current node, which in turn is less than the right descendent nodes (if any).
   对于每个节点，其左后代节点的值小于当前节点的值，而当前节点又小于右后代节点的值(如果有)。

The BST is built up on the idea of the algorithm, which allows for fast lookup, insertion and removal of nodes. The way that they are set up means that, on average, each comparison allows the operations to skip about half of the tree, so that each lookup, insertion or deletion takes time proportional to the logarithm of the number of items stored in the tree, O(log n).

BST建立在算法的基础上，该算法允许快速查找，插入和删除节点。 设置它们的方式意味着，平均而言，每个比较操作都可以跳过树的大约一半，因此每次查找，插入或删除操作所花费的时间与树中存储的项目数的对数成正比， O(log n) 。

However, some times the worst case can happen, when the tree isn’t balanced and the time complexity is O(n) for all three of these functions. That is why self-balancing trees (AVL, red-black, etc.) are a lot more effective than the basic BST.

但是，有时会发生最坏的情况，即树不平衡且所有这三个函数的时间复杂度均为O(n) 。 这就是为什么自平衡树(AVL，红黑色等)比基本BST更有效的原因。

Worst case scenario example: This can happen when you keep adding nodes that are always larger than the node before (it’s parent), the same can happen when you always add nodes with values lower than their parents.

最坏的情况示例：当您添加的节点总是大于之前的节点(它的父节点)时，可能会发生这种情况；当您添加值始终小于其父节点的节点时，也会发生这种情况。

BST的基本操作 (Basic operations on a BST)

• Create: creates an empty tree.
  创建：创建一个空树。
• Insert: insert a node in the tree.
  插入：在树中插入一个节点。
• Search: Searches for a node in the tree.
  搜索：在树中搜索节点。
• Delete: deletes a node from the tree.
  删除：从树中删除节点。

创造 (Create)

Initially an empty tree without any nodes is created. The variable/identifier which must point to the root node is initialized with a NULL value.

最初会创建一个没有任何节点的空树。 必须指向根节点的变量/标识符使用NULL值初始化。

搜索 (Search)

You always start searching the tree at the root node and go down from there. You compare the data in each node with the one you are looking for. If the compared node doesn’t match then you either proceed to the right child or the left child, which depends on the outcome of the following comparison: If the node that you are searching for is lower than the one you were comparing it with, you proceed to to the left child, otherwise (if it’s larger) you go to the right child. Why? Because the BST is structured (as per its definition), that the right child is always larger than the parent and the left child is always lesser.

您总是开始在根节点上搜索树，然后从那里向下走。 您将每个节点中的数据与要查找的节点进行比较。 如果比较的节点不匹配，那么您将继续选择右边的子节点还是左边的子节点，这取决于以下比较的结果：如果您要搜索的节点比您要比较的节点低，您将转到左侧的孩子，否则(如果较大)将转到右侧的孩子。 为什么？ 因为BST是结构化的(按照其定义)，所以右孩子总是比父孩子大，而左孩子总是小。

插 (Insert)

It is very similar to the search function. You again start at the root of the tree and go down recursively, searching for the right place to insert our new node, in the same way as explained in the search function. If a node with the same value is already in the tree, you can choose to either insert the duplicate or not. Some trees allow duplicates, some don’t. It depends on the certain implementation.

它与搜索功能非常相似。 您再次从树的根开始，然后递归地向下搜索，以与搜索功能中所述相同的方式搜索插入我们新节点的正确位置。 如果树中已经存在具有相同值的节点，则可以选择是否插入重复项。 有些树允许重复，有些则不允许。 这取决于特定的实现。

删除 (Delete)

There are 3 cases that can happen when you are trying to delete a node. If it has,

当您尝试删除节点时，可能会发生3种情况。 如果有的话

1. No subtree (no children): This one is the easiest one. You can simply just delete the node, without any additional actions required.
   无子树(无子树)：这是最简单的树。 您只需删除节点即可，而无需任何其他操作。
2. One subtree (one child): You have to make sure that after the node is deleted, its child is then connected to the deleted node’s parent.
   一个子树(一个子树)：您必须确保在删除节点后，将其子树连接到已删除节点的父树。
3. Two subtrees (two children): You have to find and replace the node you want to delete with its successor (the letfmost node in the right subtree).
   两个子树(两个子树)：必须找到要删除的节点并将其替换为其后继节点(右侧子树中的letfmost节点)。

The time complexity for creating a tree is O(1). The time complexity for searching, inserting or deleting a node depends on the height of the tree h, so the worst case is O(h).

创建树的时间复杂度为O(1) 。 搜索，插入或删除节点的时间复杂度取决于树h的高度，因此最坏的情况是O(h) 。

节点的前身 (Predecessor of a node)

Predecessors can be described as the node that would come right before the node you are currently at. To find the predecessor of the current node, look at the right-most/largest leaf node in the left subtree.

前任节点可以描述为您当前所在节点之前的节点。 要查找当前节点的前任节点，请查看左侧子树中最右侧/最大的叶节点。

节点的后继者 (Successor of a node)

Successors can be described as the node that would come right after the node you are currently at. To find the successor of the current node, look at the left-most/smallest leaf node in the right subtree.

继任者可以描述为您当前所在节点之后的节点。 要查找当前节点的后继节点，请查看右侧子树中最左侧/最小的叶节点。

特殊类型的BT (Special types of BT)

• Heap
  堆
• Red-black tree
  红黑树
• B-tree
  B树
• Splay tree
  八叉树
• N-ary tree
  N元树
• Trie (Radix tree)
  特里(基数树)

运行 (Runtime)

数据结构：数组 (Data structure: Array)

• Worst-case performance: O(log n)

  最坏情况下的性能： O(log n)

• Best-case performance: O(1)

  最佳情况下的性能： O(1)

• Average performance: O(log n)

  平均表现： O(log n)

• Worst-case space complexity: O(1)

  最坏情况下的空间复杂度： O(1)

Where n is the number of nodes in the BST.

其中n是BST中的节点数。

实施BST (Implementation of BST)

Here’s a definiton for a BST node having some data, referencing to its left and right child nodes.

这是具有一些数据的BST节点的定义，参考其左子节点和右子节点。

struct node {   int data;   struct node *leftChild;   struct node *rightChild;};

搜索操作 (Search Operation)

Whenever an element is to be searched, start searching from the root node. Then if the data is less than the key value, search for the element in the left subtree. Otherwise, search for the element in the right subtree. Follow the same algorithm for each node.

每当要搜索元素时，都从根节点开始搜索。 然后，如果数据小于键值，则在左侧子树中搜索元素。 否则，在右子树中搜索该元素。 每个节点遵循相同的算法。

struct node* search(int data){   struct node *current = root;   printf("Visiting elements: ");	   while(current->data != data){	      if(current != NULL) {         printf("%d ",current->data);			         //go to left tree         if(current->data > data){            current = current->leftChild;         }//else go to right tree         else {                            current = current->rightChild;         }			         //not found         if(current == NULL){            return NULL;         }      }			   }   return current;}

插入操作 (Insert Operation)

Whenever an element is to be inserted, first locate its proper location. Start searching from the root node, then if the data is less than the key value, search for the empty location in the left subtree and insert the data. Otherwise, search for the empty location in the right subtree and insert the data.

每当要插入元素时，请先找到其正确位置。 从根节点开始搜索，然后如果数据小于键值，则在左侧子树中搜索空位置并插入数据。 否则，请在右侧子树中搜索空白位置并插入数据。

void insert(int data) {   struct node *tempNode = (struct node*) malloc(sizeof(struct node));   struct node *current;   struct node *parent;   tempNode->data = data;   tempNode->leftChild = NULL;   tempNode->rightChild = NULL;   //if tree is empty   if(root == NULL) {      root = tempNode;   } else {      current = root;      parent = NULL;      while(1) {                         parent = current;			         //go to left of the tree         if(data < parent->data) {            current = current->leftChild;                            //insert to the left				            if(current == NULL) {               parent->leftChild = tempNode;               return;            }         }//go to right of the tree         else {            current = current->rightChild;                        //insert to the right            if(current == NULL) {               parent->rightChild = tempNode;               return;            }         }      }               }}

Binary search trees (BSTs) also give us quick access to predecessors and successors. Predecessors can be described as the node that would come right before the node you are currently at.

二进制搜索树(BST)也使我们可以快速访问前任和后继。 先前的节点可以描述为您当前所在节点之前的节点。

• To find the predecessor of the current node, look at the rightmost/largest leaf node in the left subtree. Successors can be described as the node that would come right after the node you are currently at.
  要查找当前节点的前任节点，请查看左侧子树中最右侧/最大的叶节点。 继任者可以描述为您当前所在节点之后的节点。
• To find the successor of the current node, look at the leftmost/smallest leaf node in the right subtree.
  要查找当前节点的后继节点，请查看右侧子树中最左侧/最小的叶节点。

让我们看一下在树上运行的几个过程。 (Let’s look at a couple of procedures operating on trees.)

Since trees are recursively defined, it’s very common to write routines that operate on trees that are themselves recursive.

由于树是递归定义的，因此编写对本身是递归的树进行操作的例程非常普遍。

So for instance, if we want to calculate the height of a tree, that is the height of a root node, We can go ahead and recursively do that, going through the tree. So we can say:

因此，例如，如果我们要计算树的高度(即根节点的高度)，则可以继续并递归地遍历树。 所以我们可以说：

• For instance, if we have a nil tree, then its height is a 0.
  例如，如果我们有一棵零树，那么它的高度是0。
• Otherwise, We’re 1 plus the maximum of the left child tree and the right child tree.
  否则，我们为1加上左子树和右子树的最大值。

So if we look at a leaf for example, that height would be 1 because the height of the left child is nil, is 0, and the height of the nil right child is also 0. So the max of that is 0, then 1 plus 0.

因此，例如，如果查看一片叶子，则该高度将为1，因为左子级的高度为nil，为0，而nil右级子级的高度也为0。因此，该最大值为0，则为1加0。

高度(树)算法 (Height(tree) algorithm)

if tree = nil:return 0return 1 + Max(Height(tree.left),Height(tree.right))

这是C ++中的代码 (Here is the code in C++)

int maxDepth(struct node* node){    if (node==NULL)        return 0;   else   {       int rDepth = maxDepth(node->right);       int lDepth = maxDepth(node->left);       if (lDepth > rDepth)       {           return(lDepth+1);       }       else       {            return(rDepth+1);       }   }}

We could also look at calculating the size of a tree that is the number of nodes.

我们还可以查看计算树的大小(即节点数)。

• Again, if we have a nil tree, we have zero nodes.
  同样，如果我们有一个零树，那么我们有零个节点。

Otherwise, we have the number of nodes in the left child plus 1 for ourselves plus the number of nodes in the right child. So 1 plus the size of the left tree plus the size of the right tree.

否则，我们得到左子节点中的节点数加上自己的1，再加上右子节点中的节点数。 所以1加左树的大小再加上右树的大小。

大小(树)算法 (Size(tree) algorithm)

if tree = nilreturn 0return 1 + Size(tree.left) + Size(tree.right)

这是C ++中的代码 (Here is the code in C++)

int treeSize(struct node* node){    if (node==NULL)        return 0;    else        return 1+(treeSize(node->left) + treeSize(node->right));}

freeCodeCamp YouTube频道上的相关视频 (Relevant videos on freeCodeCamp YouTube channel)

以下是二叉树的常见类型： (Following are common types of Binary Trees:)

Full Binary Tree/Strict Binary Tree: A Binary Tree is full or strict if every node has exactly 0 or 2 children.

完整的二叉树/严格的二叉树：如果每个节点恰好具有0或2个子节点，则二叉树是完整的或严格的。

18       /       \       15         30      /  \        /  \  40    50    100   40

In Full Binary Tree, number of leaf nodes is equal to number of internal nodes plus one.

在完整二叉树中，叶节点数等于内部节点数加一。

Complete Binary Tree: A Binary Tree is complete Binary Tree if all levels are completely filled except possibly the last level and the last level has all keys as left as possible

完整的二叉树：如果所有级别都已完全填充，则二叉树就是完整的二叉树，除了最后一个级别，并且最后一个级别的所有键都尽可能保留

18       /       \       15         30      /  \        /  \  40    50    100   40 /  \   /8   7  9

翻译自:

二进制搜索树