二叉查找树(二叉排序树)

2013-01-15 17:58:18   最后更新: 2015-08-06 23:24:17   访问数量:806




 

对于二叉树的任一节点,如果该节点的左子树都小于他,右子树都大于他,这棵树即被称为“二叉查找树”,又称“二叉排序树”

因此,二叉查找树的中序遍历将产生一个由小到大的有序数列

需要注意的是,树的递归式遍历的时间复杂度是O(n)

 

/* * file: function.h * author: 龙泉居士 * date: 2013-01-15 17:58 */ #ifndef FUNCTION_H_20130113 #define FUNCTION_H_20130113 #include <vector> using std::vector; class Search_tree { private: struct Node { Node(); int value; Node *left; Node *right; Node *father; }; Node *root; public: Search_tree (); Search_tree (vector<int>); void insert(int); void remove(Node *); void remove(int); void clear(); Node* find (int); Node* get_left(Node*); Node* get_right(Node*); Node* get_father(Node*); int get_value(Node *); void pre_print(); void mid_print(); ~Search_tree (); }; #endif

 

 

/* * file: function.cc * author: 龙泉居士 * date: 2013-01-15 18:15 */ #include <iostream> #include <vector> #include <stack> #include "function.h" using namespace std; Search_tree::Search_tree():root(NULL) { } Search_tree::Search_tree(vector<int> ivec) { if (ivec.size() > 0) for (size_t i=0; i<ivec.size(); ++i) insert(ivec.at(i)); } void Search_tree::insert (int v) { Node *n = new Node; n -> value = v; if (root == NULL) root = n; else { Node *tmp = root; Node *tmpn = tmp; while (tmp != NULL) { tmpn = tmp; if (v <= tmp->value) tmp = tmp->left; else tmp = tmp->right; } n->father = tmpn; if (v <= tmpn->value) tmpn -> left = n; else tmpn -> right = n; } } void Search_tree::remove (Node *n) { if (n == NULL) return; Node *tmpn = n; Node *tmp = n->right; while (tmp != NULL) { tmpn = tmp; tmp = tmpn->left; } if (tmpn == n) { if (tmpn->value <= tmpn->father->value) tmpn->father->left = tmpn->left; else tmpn->father->right = tmpn->right; tmpn->right->father = tmpn->father; } else if (tmpn->father != n) { n->value = tmpn->value; tmpn->father->left = tmpn->right; if (tmpn -> right != NULL) tmpn->right->father = tmpn->father; } else { n->value = tmpn -> value; n->right = tmpn->right; if (tmpn -> right != NULL) tmp -> right -> father = tmpn -> father; } delete tmpn; } Search_tree::Node* Search_tree::find (int v) { Node *tmp = root; while (tmp != NULL) { if (v == tmp->value) return tmp; else if (v < tmp->value) tmp = tmp->left; else tmp = tmp->right; } return NULL; } void Search_tree::remove (int v) { remove(find(v)); } Search_tree::Node *Search_tree::get_left (Search_tree::Node *n) { if (n != NULL) return n->left; return NULL; } Search_tree::Node *Search_tree::get_right (Search_tree::Node *n) { if (n != NULL) return n->right; return NULL; } Search_tree::Node *Search_tree::get_father (Search_tree::Node *n) { if (n != NULL) return n->father; return NULL; } int Search_tree::get_value (Search_tree::Node *n) { if (n != NULL) return n->value; cerr << "get_value Param error" << endl; return 0; } void Search_tree::pre_print() { Search_tree::Node *n = root; stack<Search_tree::Node *> s; while (1) { while (n!=NULL) { cout << n->value << ' ' << flush; s.push(n); n = n->left; } n = s.top()->right; s.pop(); if (s.empty() && n==NULL) break; } cout << endl; } void Search_tree::mid_print() { Search_tree::Node *n = root; stack<Search_tree::Node *> s; while (1) { while (n!=NULL) { s.push (n); n = n->left; } n = s.top(); cout << n->value << ' ' << flush; n = n->right; s.pop(); if (s.empty() && n==NULL) break; } cout << endl; } void Search_tree::clear () { Search_tree::Node *n = root; stack<Search_tree::Node *> s; while (1) { while (n!=NULL) { s.push (n); n = n->left; } n = s.top() -> right; delete s.top(); s.pop(); if (s.empty() && n==NULL) break; } root = NULL; } Search_tree::~Search_tree () { Search_tree::Node *n = root; stack<Search_tree::Node *> s; while (1) { while (n!=NULL) { s.push (n); n = n->left; } n = s.top()->right; delete s.top(); s.pop(); if (s.empty() && n==NULL) break; } } Search_tree::Node::Node():left(NULL), right(NULL), father(NULL) { }

 

 

如声明中那样,我选择为之实现了一些基本的功能:两个构造函数、添加元素、两个重载的删除操作、清空操作、查找元素以及前序和中序遍历等基本的操作

这些操作都是非常简单的基本操作,其中的遍历算法稍显复杂,需要多进行理解,在理解的基础上还是十分简单的,当然,我没有选择实现基于递归的遍历算法版本

这些算法中比较复杂的要数删除元素的算法,因为在删除后还要保证二叉查找树的结构,所以需要考虑到子树的连接问题

对于算出元素的算法,最简单的方法是将被删除元素的子树使用insert算法重新添加到删除元素后的树结构中,这样的解决方案对实现来说是非常容易的,但是由此造成一个问题,那就是很可能造成某个子树的长度会非常长,这对于遍历、查找等操作来说会极大的增加其时间复杂度,所以显然这不是一个好的解决方案

理想的方案是要让树结构的变化尽量小,当然了,让树平衡就不是二叉查找树的任务了

 

算法导论

算法导论中采用了如下的解决方案:

分为三种情况:

 

  1. 第一种情况,要删除的节点没有子节点,这样,直接删除该节点就可以了
  2. 第二种情况,该节点只有一条子树,这样只要删掉该节点并把他的这一条子树接在他的原父节点就可以了
  3. 第三种情况,要删除的节点既有左子树又有右子树,这样是比较复杂的情况,途中还是画的比较清楚的

 

我的算法

我的代码中的解决方案也是分为三种情况:

 

 

思路来源于第三种情况的分析:

第三种情况的解决方法是:找到树中被删除元素的子树中大于被删除元素的最小元素,然后将它与被删除元素替换,那么,怎么找这个元素呢?这个元素一定是被删除元素的右子树的最左端叶子节点,因此情况可以分成三类:

  1. 被删除元素没有右子树,也就没有替换元素了,这是只要将被删除元素删除,然后将左子树放到他父亲节点的下面
  2. 替换元素刚好是被删除元素的右孩子,这样的话,这个右孩子必定没有左子树,所以只要用这个右孩子替换被删除元素,然后将替换元素的右子树变成被删除元素的右子树,然后删掉替换元素就可以了
  3. 替换元素是被删除元素的右子树的最左端叶子节点,与情况2一样, 这个替换元素一定是没有左子树的并且他是父亲的左孩子,这样,只要用替换元素的值替换被删除元素,并将替换元素的右子树变成父亲的左子树,然后删掉替换元素就可以了

 






读书笔记      技术帖      算法      算法导论      c语言      数据结构      struct      龙潭书斋      排序      search      二叉树      查找      sort      二叉查找树     


京ICP备15018585号