算法導論-----------二叉搜尋樹

先上二叉樹查找樹的删除的代碼，因為删除是二叉查找樹最複雜的操作：

int BinarySearchTree<T>::tree_remove(const T& elem)
{
  BinarySearchTreeNode<T> *z = tree_search(elem);//根據元素查找到要删除的節點
  BinarySearchTreeNode<T> *x, *y;

  if (z != NULL)
  {
    //用y來表示實際要删除的節點
    if (z->left == NULL || z->right == NULL)//最多隻有一個兒子節，要麼沒有兒子節點
      y = z;
    else
      y = tree_search(tree_successor(elem));//有兩個兒子的時候實際删除的是後繼節點

    //因為有上面的if語句，是以y要麼隻有一個兒子，要麼沒有兒子。後繼節點隻有右兒子或者沒有兒子
    //是以x要麼是兒子節點，要麼是空節點
    if (y->left != NULL)
      x = y->left;
    else
      x = y->right;

    if (x != NULL)//判斷y節點有沒有兒子節點，有的花就把y節點的父節點變成x的父節點。
      x->parent = y->parent;

        //y是根節點或者不是根節點的情況
    if (y->parent == NULL)
      root = x;
    else if (y == y->parent->left)//如果y節點不是根節點的情況該怎麼處理呢？
      y->parent->left = x;
    else
      y->parent->right = x;

    //處理後繼節點的情況，因為y表示後繼的時候y！=z；
    if (y != z)
      z->elem = y->elem;
    delete y;
  }

  return -1;
}

二叉查找樹的概念及操作。主要内容包括二叉查找樹的性質，如何在二叉查找樹中查找最大值、最小值和給定的值，如何找出某一個元素的前驅和後繼，如何在二叉查找樹中進行插入和删除操作。在二叉查找樹上執行這些基本操作的時間與樹的高度成正比，一棵随機構造的二叉查找樹的期望高度為O(lgn)，進而基本動态集合的操作平均時間為θ(lgn)。

1、二叉查找樹

設x為二叉查找樹中的一個結點。如果y是x的左子樹中的一個結點，則key[y]≤key[x]。如果y是x的右子樹中的一個結點，則key[x]≤key[y]。根據二叉查找樹的特征可知，采用中根周遊一棵二叉查找樹，可以得到樹中關鍵字有小到大的序列。

一棵二叉樹查找及其中根周遊結果如下圖所示：

如果x是一棵包含n個結點的子樹的根，則其中根周遊運作時間為θ(n)。

問題：二叉查找樹性質與最小堆之間有什麼差別？能否利用最小堆的性質在O(n)時間内，按序輸出含有n個結點的樹中的所有關鍵字？

2、查詢二叉查找樹

　　二叉查找樹中最常見的操作是查找樹中的某個關鍵字，除了基本的查詢，還支援最大值、最小值、前驅和後繼查詢操作，書中就每種查詢進行了詳細的講解。

（1）查找SEARCH

　　在二叉查找樹中查找一個給定的關鍵字k的過程與二分查找很類似，根據二叉查找樹在的關鍵字存放的特征，很容易得出查找過程：首先是關鍵字k與樹根的關鍵字進行比較，如果k大比根的關鍵字大，則在根的右子樹中查找，否則在根的左子樹中查找，重複此過程，直到找到與遇到空結點為止。例如下圖所示的查找關鍵字13的過程：（查找過程每次在左右子樹中做出選擇，減少一半的工作量）

書中給出了查找過程的遞歸和非遞歸形式的僞代碼：

TREE_SEARCH(x,k)
  if x=NULL or k=key[x]
      then return x
  if(k<key[x])
      then return TREE_SEARCH(left[x],k)
   else
      then return TREE_SEARCH(right[x],k)

ITERATIVE_TREE_SEARCH(x,k)
  while x!=NULL and k!=key[x]
      do if k<key[x]
              then x=left[x]
           else
              then x=right[x]
   return x

（2）查找最大關鍵字和最小關鍵字

　　根據二叉查找樹的特征，很容易查找出最大和最小關鍵字。查找二叉樹中的最小關鍵字：從根結點開始，沿着各個節點的left指針查找下去，直到遇到NULL時結束。如果一個結點x無左子樹，則以x為根的子樹中，最小關鍵字就是key[x]。查找二叉樹中的最大關鍵字：從根結點開始，沿着各個結點的right指針查找下去，直到遇到NULL時結束。書中給出了查找最大最小關鍵字的僞代碼：

TREE_MINMUM(x)

while left[x] != NULL

 do x=left[x]

return x

TREE_MAXMUM(x)

while right[x] != NULL

do x= right[x]

return x

（3）前驅和後繼

　　給定一個二叉查找樹中的結點，找出在中序周遊順序下某個節點的前驅和後繼。如果樹中所有關鍵字都不相同，則某一結點x的前驅就是小于key[x]的所有關鍵字中最大的那個結點，後繼即是大于key[x]中的所有關鍵字中最小的那個結點。根據二叉查找樹的結構和性質，不用對關鍵字做任何比較，就可以找到某個結點的前驅和後繼。

　　查找前驅步驟：先判斷x是否有左子樹，如果有則在left[x]中查找關鍵字最大的結點，即是x的前驅。如果沒有左子樹，則從x繼續向上執行此操作，直到遇到某個結點是其父節點的右孩子結點。例如下圖查找結點7的前驅結點6過程：

　　查找後繼步驟：先判斷x是否有右子樹，如果有則在right[x]中查找關鍵字最小的結點，即使x的後繼。如果沒有右子樹，則從x的父節點開始向上查找，直到遇到某個結點是其父結點的左兒子的結點時為止。例如下圖查找結點13的後繼結點15的過程：

書中給出了求x結點後繼結點的僞代碼:

TREE_PROCESSOR(x)
    if right[x] != NULL
        then return TREE_MINMUM(right(x))
    y=parent[x]
    while y!= NULL and x ==right[y]
           do x = y
               y=parent[y]
    return y

定理：對一棵高度為h的二叉查找，動态集合操作SEARCH、MINMUM、MAXMUM、SUCCESSOR、PROCESSOR等的運作時間均為O(h)。

3、插入和删除

　　插入和删除會引起二叉查找表示的動态集合的變化，難點在在插入和删除的過程中要保持二叉查找樹的性質。插入過程相當來說要簡單一些，删除結點比較複雜。

（1）插入

　　插入結點的位置對應着查找過程中查找不成功時候的結點位置，是以需要從根結點開始查找帶插入結點位置，找到位置後插入即可。下圖所示插入結點過程：

書中給出了插入過程的僞代碼：

TREE_INSERT(T,z)
    y = NULL;
    x =root[T]
    while x != NULL
        do y =x
            if key[z] < key[x]
                 then x=left[x]
                 else  x=right[x]
     parent[z] =y
     if y=NULL
        then root[T] =z
        else if key[z]>key[y]
                   then  keft[y]  = z
                   else   right[y] =z

插入過程運作時間為O(h)，h為樹的高度。

（2）删除

　　從二叉查找樹中删除給定的結點z，分三種情況讨論：

<1>結點z沒有左右子樹，則修改其父節點p[z]，使其為NULL。删除過程如下圖所示：

<2>如果結點z隻有一個子樹（左子樹或者右子樹），通過在其子結點與父節點建立一條鍊來删除z。删除過程如下圖所示：

<3>如果z有兩個子女，則先删除z的後繼y（y沒有左孩子），在用y的内容來替代z的内容。

書中給出了删除過程的僞代碼：

TREE_DELETE(T,z)
    if left[z] ==NULL or right[z] == NULL
       then y=z
       else  y=TREE_SUCCESSOR(z)
   if left[y] != NULL
       then x=left[y]
       else  x=right[y]
   if x!= NULL
       then parent[x] = parent[y]
   if p[y] ==NULL
      then root[T] =x
      else if y = left[[prarnt[y]]
                  then left[parent[y]] = x
                  else  right[parent[y]] =x
    if y!=z
        then key[z] = key[y]
              copy y's data into z
     return y

定理：對高度為h的二叉查找樹，動态集合操作INSERT和DELETE的運作時間為O(h)。

4、實作測試

　　采用C++語言實作一個簡單的二叉查找樹，支援動态集合的基本操作：search、minmum、maxmum、predecessor、successor、insert和delete。設計的二叉查找樹結構如下所示：

template<class T>
class BinarySearchTreeNode
{
public:
  T elem;
  BinarySearchTreeNode<T> *parent;
  BinarySearchTreeNode<T> *left;
  BinarySearchTreeNode<T> *right;
};

template<class T>
class BinarySearchTree
{
public:
  BinarySearchTree();
  void tree_insert(const T& elem);
  int tree_remove(const T& elem);
  BinarySearchTreeNode<T> *tree_search(const T& elem) const;
  T tree_minmum(BinarySearchTreeNode<T>* root) const;
  T tree_maxmum(BinarySearchTreeNode<T>* root) const;
  T tree_successor(const T& elem) const;
  T tree_predecessor(const T& elem) const;
  int empty() const;
  void inorder_tree_walk() const;
  BinarySearchTreeNode<T>* get_root() { return root; }

private:
  BinarySearchTreeNode<T>* root;
};

完整程式如下所示：

#include<iostream>
#include<stack>

using namespace std;
/*-----------------------------------------------------------------------------------------------*/
/*采用C++語言實作一個簡單的二叉查找樹，支援動态集合的基本操作：                                      */
/*search、minmum、maxmum、predecessor、successor、insert和delete。設計的二叉查找樹結構如下所示：    */
/*------------------------------------------------------------------------------------------------*/

template<class T>
class BinarySearchTreeNode
{
public:
  T elem;
  BinarySearchTreeNode<T> *parent;
  BinarySearchTreeNode<T> *left;
  BinarySearchTreeNode<T> *right;
};

template<class T>
class BinarySearchTree
{
public:
  BinarySearchTree();
  void tree_insert(const T& elem);
  int tree_remove(const T& elem);
  BinarySearchTreeNode<T> *tree_search(const T& elem) const;
  T tree_minmum(BinarySearchTreeNode<T>* root) const;
  T tree_maxmum(BinarySearchTreeNode<T>* root) const;
  T tree_successor(const T& elem) const;
  T tree_predecessor(const T& elem) const;
  int empty() const;
  void inorder_tree_walk() const;
  BinarySearchTreeNode<T>* get_root() { return root; }

private:
  BinarySearchTreeNode<T>* root;
};

//構造函數，初始化二叉查找樹。
template <class T>
BinarySearchTree<T>::BinarySearchTree()
{
  root = NULL;
}


template <class T>
void BinarySearchTree<T>::tree_insert(const T& elem)
{
  if (!empty())
  {
    BinarySearchTreeNode<T> *p_node = root;
    BinarySearchTreeNode<T> *q_node = NULL;
    BinarySearchTreeNode<T> *new_node = new BinarySearchTreeNode<T>;

    new_node->elem = elem;
    new_node->left = NULL;
    new_node->right = NULL;
    new_node->parent = NULL;

    while (p_node)
    {
      q_node = p_node;
      if (p_node->elem > elem)
        p_node = p_node->left;
      else
        p_node = p_node->right;
    }//當p_node為空的時候，q_node正好是正确的插入位置的父節點，且q_node是葉節點.

    if (q_node->elem > elem)
      q_node->left = new_node;
    else
      q_node->right = new_node;
    new_node->parent = q_node;
  }
  else
  {
    root = new BinarySearchTreeNode<T>;
    root->elem = elem;
    root->parent = NULL;
    root->left = NULL;
    root->right = NULL;
  }
}

//二叉查找樹節點的删除
template <class T>
int BinarySearchTree<T>::tree_remove(const T& elem)
{
  BinarySearchTreeNode<T> *z = tree_search(elem);
  BinarySearchTreeNode<T> *x, *y;

  if (z != NULL)
  {
    //用y來表示實際要删除的節點
    if (z->left == NULL || z->right == NULL)//最多隻有一個兒子節，要麼沒有兒子節點
      y = z;
    else
      y = tree_search(tree_successor(elem));//有兩個兒子的時候實際删除的是後繼節點

    //因為有上面的if語句，是以y要麼隻有一個兒子，要麼沒有兒子。後繼節點隻有右兒子或者沒有兒子
    //是以x要麼是兒子節點，要麼是空節點
    if (y->left != NULL)
      x = y->left;
    else
      x = y->right;

    if (x != NULL)
      x->parent = y->parent;

    if (y->parent == NULL)
      root = x;
    else if (y == y->parent->left)
      y->parent->left = x;
    else
      y->parent->right = x;

    //處理後繼節點的情況，因為y表示後繼的時候y！=z；
    if (y != z)
      z->elem = y->elem;
    delete y;
  }

  return -1;
}


//  BinarySearchTreeNode<T>* 傳回類型，傳回查找元素elem的節點
template <class T>
BinarySearchTreeNode<T>* BinarySearchTree<T>::tree_search(const T& elem) const
{
  BinarySearchTreeNode<T> *pnode = root;
  while (pnode)
  {
    if (pnode->elem == elem)
      break;
    else if (pnode->elem > elem)
      pnode = pnode->left;
    else
      pnode = pnode->right;
  }

  return pnode;
}

//傳回最小關鍵字的元素，可以參考書上用遞歸方法的寫
template <class T>
T BinarySearchTree<T>::tree_minmum(BinarySearchTreeNode<T>* root) const
{
  BinarySearchTreeNode<T> *pnode = root;
  
  while (pnode->left)
    pnode = pnode->left;
  return pnode->elem;
}

//傳回最大關鍵字的元素，可以改用遞歸，不過效率降低
template <class T>
T BinarySearchTree<T>::tree_maxmum(BinarySearchTreeNode<T>* root) const
{
  BinarySearchTreeNode<T> *pnode = root;

  while (pnode->right != NULL)
    pnode = pnode->right;

  return pnode->elem;
}


//後繼節點
template <class T>
T BinarySearchTree<T>::tree_successor(const T& elem) const
{
  BinarySearchTreeNode<T>* pnode = tree_search(elem);
  BinarySearchTreeNode<T>* parentnode;
  if (pnode != NULL)
  {
    if (pnode->right)
      return tree_minmum(pnode->right);
    parentnode = pnode->parent;
    while (parentnode && pnode == parentnode->right)
    {
      pnode = parentnode;
      parentnode = parentnode->parent;
    }
    if (parentnode)
      return parentnode->elem;
    else
      return T();
  }
  return T();
}

//前繼節點
template <class T>
T BinarySearchTree<T>::tree_predecessor(const T& elem)const
{
  BinarySearchTreeNode<T>* pnode = tree_search(elem);
  BinarySearchTreeNode<T>* parentnode;
  if (pnode != NULL)
  {
    if (pnode->right)
      return tree_maxmum(pnode->right);
    parentnode = pnode->parent;
    while (parentnode && pnode == parentnode->left)
    {
      pnode = parentnode;
      parentnode = pnode->parent;
    }
    if (parentnode)
      return parentnode->elem;
    else
      return T();
  }
  return T();
}

template <class T>
int BinarySearchTree<T>::empty() const
{
  return (NULL == root);
}


//按照大小順序輸出二叉查找樹，即中根周遊的方法輸出二叉查找樹.使用stack功能的實作。
template <class T>
void BinarySearchTree<T>::inorder_tree_walk() const
{
  if (NULL != root)
  {
    stack<BinarySearchTreeNode<T>*> s;
    BinarySearchTreeNode<T> *P_temp;
    P_temp = root;
    while (NULL != P_temp || !s.empty())
    {
      if (NULL != P_temp)
      {
        s.push(P_temp);
        P_temp = P_temp->left;
      }
      else
      {
        P_temp = s.top();
        s.pop();
        cout << P_temp->elem << " ";
        P_temp = P_temp->right;
      }
    }
  }
}

int main()
{
  BinarySearchTree<int> bstree;
  BinarySearchTreeNode<int>* ptnode, *proot;
  bstree.tree_insert(32);
  bstree.tree_insert(21);
  bstree.tree_insert(46);
  bstree.tree_insert(54);
  bstree.tree_insert(16);
  bstree.tree_insert(38);
  bstree.tree_insert(70);
  cout << "inorder tree walk is: ";
  bstree.inorder_tree_walk();
  proot = bstree.get_root();
  cout << "\nmax value is: " << bstree.tree_maxmum(proot) << endl;
  cout << "min value is: " << bstree.tree_minmum(proot) << endl;
  ptnode = bstree.tree_search(38);
  if (ptnode)
    cout << "the element 38 is exist in the binary tree.\n";
  else
    cout << "the element 38 is not exist in the binary tree.\n";
  cout << "the successor of 38 is: " << bstree.tree_successor(38) << endl;
  cout << "the predecessor of 38 is:" << bstree.tree_predecessor(38) << endl;
  if (bstree.tree_remove(46) == 0)
    cout << "delete 46 successfully" << endl;
  else
    cout << "delete 46 failed" << endl;
  cout << "inorder tree walk is: ";
  bstree.inorder_tree_walk();
  exit(0);
}

程式測試結果如下所示：

算法導論-----------二叉搜尋樹

繼續閱讀

FZU 1064 教授的測試

CSU 1811 Tree Intersection

圖解

二進制碼和格雷碼轉換問題

java代碼分治法求解最大子數組問題

算法導論讀書筆記（6）堆排序第二部分排序和順序統計量

算法導論---堆排序Java代碼實作

[算法導論]堆排序堆參考

算法導論---堆排序

算法導論之堆排序相關

算法導論 - 堆排序堆排序

算法導論的C實作——堆排序堆最大堆維護最大堆建堆排序

算法導論第6章堆排序算法導論第6章堆排序

【算法導論】堆排序一、數組轉換成堆二、如何進行堆排序三、堆排序過程四、堆排序時間複雜度

經典查找算法之二分查找

查找算法之二分查找查找算法之二分查找