ITEEDU

BST二叉搜索树

二叉搜索树(Binary Search Tree,BST)

1.所有非叶子结点至多拥有两个儿子(Left和Right);

2.所有结点存储一个关键字;

3.非叶子结点的左指针指向小于其关键字的子树,右指针指向大于其关键字的子树;

如:

BST树的搜索,从根结点开始,如果查询的关键字与结点的关键字相等,那么就命中;

否则,如果查询关键字比结点关键字小,就进入左儿子;如果比结点关键字大,就进入右儿子;如果左儿子或右儿子的指针为空,则报告找不到相应的关键字;

如果BST树的所有非叶子结点的左右子树的结点数目均保持差不多(平衡),那么B树的搜索性能逼近二分查找;但它比连续内存空间的二分查找的优点是,改变BST树结构(插入与删除结点)不需要移动大段的内存数据,甚至通常是常数开销;

如:

但BST树在经过多次插入与删除后,有可能导致不同的结构:

右边也是一个BST树,但它的搜索性能已经是线性的了;同样的关键字集合有可能导致不同的树结构索引;所以,使用BST树还要考虑尽可能让BST树保持左图的结构,和避免右图的结构,也就是所谓的“平衡”问题;

BST查找操作

BSTNode* bst_search(BSTNode* node, int value) {
  while(node != NULL) {
    if(value < node->value) // 向左 
      node = node->left;
    else if(value > node->value) // 向右 
      node = node->right;
    else // 找到 
      return node;
  }
  return NULL; // 失败 
}

BST树的插入操作

首先找到插入的位置,要么向左,要么向右,直到找到空结点,即为插入位置,如果找到了相同值的结点,插入失败。

伪代码:

TREE-INSERT(T, z)
 1  y ← nil[T]                 // y 始终指向 x 的父结点。
 2  x ← root[T]              // x 指向当前树的根结点,
 3  while x ≠ nil[T]
 4      do y ← x
 5         if key[z] < key[x]   //向左,向右..
 6            then x ← left[x]
 7            else x ← right[x] // 为了找到合适的插入点,x 探路跟踪路径,直到x成为NIL 为止。
 8  p[z] ← y         // y置为 插入结点z 的父结点。
 9  if y = nil[T]
10     then root[T] ← z
11     else if key[z] < key[y]
12             then left[y] ← z
13             else right[y] ← z //此 8-13行,置z 相关的指针。

C代码:

bool bst_insert(BSTNode*& root, int value) {
  BSTNode* pre = NULL;
  BSTNode* curr = root;
  while(curr != NULL) {
    if(value < curr->value) { // 向左 
      pre = curr;
      curr = curr->left;
    }
    else if(value > curr->value) { // 向右 
      pre = curr;
      curr = curr->right; 
    }
    else // 失败 
      return false;
  }
  curr = new BSTNode; // 插入 
  curr->value = value;
  curr->left = curr->right = NULL;
  if(pre == NULL)
    root = curr;
  else

    curr->value < pre->value ? pre->left=curr : pre->right=curr;
  return true;
}

BST删除操作

相对查找和插入复杂一点,根据待删除结点的孩子情况,分三种情况:没有孩子,只有一个孩子,有两个孩子。

1.没有孩子的情况,其父结点指向空,删除该结点。

2.有一个孩子的情况,其父结点指向其孩子,删除该结点。

3.有两个孩子的情况,当前结点要用其它结点替换,然后释放当前结点。

用左子树中的最大元素替换当前结点。左子树一直right到nil,可能有左节点。

用右子树中的最小结点替换当前结点。右子树一直left到nil,可能有右节点。

伪代码:

TREE-SUCCESSOR(z)为中序遍历z的后继节点,为z右子树中的最小结点

TREE-DELETE(T, z)
 1 if left[z] = NIL or right[z] = NIL
 2    then y ← z
 3    else y ← TREE-SUCCESSOR(z)
 4 if left[y] ≠ NIL
 5    then x ← left[y]
 6    else x ← right[y]
 7 if x≠NIL
 8    then p[x] ← p[y]
 9 if p[y] = NIL
10    then root[T] ← x
11    else if y = left[p[y]]
12            then left[p[y]] ← x
13            else right[p[y]] ← x
14 if y ≠ z
15    then key[z] ← key[y]
16         copy y's satellite data into z 
17 return y  

C代码:

bool bst_delete(BSTNode*& node, int value) {
  BSTNode* parent = NULL;
  BSTNode* tmp;
  while(node != NULL) {
    if(value < node->value) { // 向左 
      parent = node;
      node = node->left;
    }
    else if(value > node->value) { // 向右 
      parent = node;
      node = node->right;
    }
    else { // 找到了 
      if(NULL==node->left && NULL==node-right) { // 叶子结点         
        if(parent == NULL) { // 根结点 
          delete node;
          node = NULL;
        }
        else { // 非根结点 
          (parent->left==node)?(parent->left=NULL):(parent->right=NULL);
          delete node;
          node = NULL;
        }        
      }
      else if(NULL!=node->left && NULL==node->right) { // 只有左孩子
        if(parent == NULL) { // 根结点 
          tmp = node;
          node = node->left;
          delete tmp;          
        }
        else { // 非根结点 
          (parent->left==node)?(parent->left=node->left):(parent->right=node->left);
          delete node;
        }
      }
      else if(NULL!=node->right && NULL==node->left) { // 只有右孩子 
        if(parent == NULL) { // 根结点 
          tmp = node;
          node = node->right;
          delete tmp;          
        }
        else { // 非根结点 
          (parent->left==node)?(parent->left=node->right):(parent->right=node->right);
          delete node;
        }
      }
      else { // 既有左孩子也有右孩子 
        BSTNode* leftNode = node;
        while(leftNode->right != NULL) {
          parent = leftNode;
          leftNode = leftNode->right;
        }
        // 交换leftNode与node
        int swapValue = leftNode->value;
        leftNode->value = node->value;
        node->value = swapValue;
        // 删除leftNode,parent肯定不为空 
        (parent->left==node)?(parent->left=NULL):(parent->right=NULL);
        delete node;
      }
    }
  }
  return false; // 失败
}