二进制搜索树


难度级别 易得奖学金
经常问 亚马逊 DBOI 风筝 印孚瑟斯 微软
二进制搜索树 二叉树 理论

二叉树是二叉树 某些规则使我们能够以排序的方式维护数据。

因为它是一个 二叉树 因此,一个节点最多可以有2个子节点。

二叉搜索树节点的结构

 

二进制搜索树

二叉树成为二叉搜索树的规则

  1. 节点左子树中存在的节点应小于该节点。
  2. 节点的右子树中存在的节点应大于该节点。
  3. 以上两个条件对于树中的所有节点均应为真。

使用案列

二进制搜索树

Left subtree of 8 contains: 5, 3, 7 which are smaller than 8

Right subtree of 8 contains: 16, 18 which are greater than 8

Left subtree of 5 contains: 3 which is smaller than 5

Right subtree of 5 contains: 7 which is greater than 5

Left subtree of 16 does not contain any node.

Right subtree of 16 contains: 18 which is greater than 16

3, 7, 18 are leaf nodes hence there will be no left and right subtree present.

始终记得检查每个节点的BST条件。

例如:

这不是二进制搜索树。

二进制搜索树

二叉搜索树的优点

  1. 可以在O(log(h))中进行搜索,其中h是BST的高度,因为我们可以使用将数据按排序方式存储在BST中的属性对其进行二进制搜索。
  2. 以排序方式插入数据也是在O(log(h))中完成的,而其他数据结构(如数组和链表)则需要O(n)的时间。

二进制搜索树的创建

算法

  1. 用要插入的值创建一个节点
  2. insertBST(节点,值)
    1. 如果root == NULL,则返回创建的节点
    2. 如果root-> value <键:
      • 将创建的节点插入右侧的子树中
      • root-> right = insertBST(root-> right,value)
    3.  如果root-> value>键:
      • 在左侧子树中插入创建的节点
      • root-> left = insertBST(root-> left,value)
  1. 返回根

让我们通过一个例子来理解它:

考虑一个整数数组[4,7,2,8,5]

让我们通过从数组中依次获取每个元素来创建BST

步骤1: 插入4

由于根为空,因此使新创建的节点为根。

二进制搜索树

步骤2: 插入7

根值为4,因此7应该在根的右边。

二进制搜索树

步骤3: 插入2

根值为4,因此应在根的左侧放置2。

步骤4: 插入8

根值为4,因此应在根的右侧放置8。

现在我们将检查7,因为7 <8,因此8应该放在7的右边。

步骤5: 插入5

根值为4,因此应在根的右侧放置5。

现在我们将检查7,因为7> 5,因此应在5的左侧放置7。

二叉搜索树的实现

C ++程序

#include<bits/stdc++.h>
using namespace std;

struct node
{
    int value;
    struct node* left;
    struct node* right;
    node(int value){             // constructor
        this->value = value;
        this->left = NULL;
        this->right = NULL;
    }
};
struct node* insertBST(node* root, int value)
{
    if (root == NULL) 
        return new node(value);                       // return newly created node

    if (value < root->value)                         // value should be inserted in the left subtree
        root->left  = insertBST(root->left, value);
    else if (value > root->value)                    // value should be inserted in the right subtree
        root->right = insertBST(root->right, value);   
    return root;
}

void inorder(node* root){
    if(root == NULL) 
        return;
    inorder(root->left);
    cout<<root->value<<"-> ";
    inorder(root->right);
}


int main(){
    node *root = NULL;
    root = insertBST(root, 10);     //make the first created node as root
    insertBST(root, 5);
    insertBST(root, 4);
    insertBST(root, 16);
    insertBST(root, 2);
    insertBST(root, 12);
    insertBST(root, 17);

    inorder(root);
}

JAVA程序

class Node { 
    int value; 
    Node left, right; 
  
    public Node(int v) { //constructor
        value = v; 
        left = null;
        right = null; 
    } 
};
class Main { 
    public static Node insertBST(Node root, int value) { 
        if (root == null) { 
            return new Node(value);                            // return newly created node
        }
        if (value < root.value)                               // value should be inserted in the left subtree
            root.left = insertBST(root.left, value); 
        else if (value > root.value)                         // value should be inserted in the right subtree
            root.right = insertBST(root.right, value); 
        return root; 
    } 
    public static void inorder(Node root) { 
        if (root != null) { 
            inorder(root.left); 
            System.out.print(root.value+"-> "); 
            inorder(root.right); 
        } 
    } 
    public static void main(String[] args) { 
        Node root = null; 
        
        root = insertBST(root, 10); //make the first created node as root 
        insertBST(root, 5); 
        insertBST(root, 4); 
        insertBST(root, 16); 
        insertBST(root, 2); 
        insertBST(root, 12); 
        insertBST(root, 17); 
        
        inorder(root);
    } 
}
2-> 4-> 5-> 10-> 12-> 16-> 17-> 

创建的树的结构

參考資料