这些功能足以保持二进制搜索树的平衡吗?

我有一些功能,对于使BST树保持平衡的这些基本原理中有多少,我感到怀疑。

这是代码

static int maxKey = 1000;
typedef int Key;
class Item {
private:
    Key keyval;
public:
    Item() { 
        keyval = maxKey; 
    }
    Key key() const { 
        return keyval;
    }
    bool null() { return keyval == maxKey; }
    bool scan(istream& is = cin) {
        is >> keyval;
        return(!cin.fail());
    }
    //Print values of info and keyval
    void show(ostream& os = cout) {
        os << keyval << endl;
    }
};

template <typename Item, typename Key>
class BST {
private:
    //This is the struct to represent nodes of the tree
    struct node {
        Item item;
        node* l; node* r;
        node(Item it) { item = it; l = 0; r = 0; }
    };
    typedef node* link;
    link head;
    Item nullItem;

    int tree_size(link tree){
        if(!tree) return 0;
        return 1+tree_size(tree->r)+tree_size(tree->l);
        }
    //Right rotation
    void rotR(link& h) { 
        link x = h->l; //Create a temp node equal to left child of root (it will become new root)
        h->l = x->r; //Left child of root become right child of temp node
        x->r = h; //Right child of temp node become root
        h = x; //Root become temp node
    }
    //Left rotation
    void rotL(link& h) { 
        link x = h->r; //Create a temp node equal ro right child of root (it will became new root)
        h->r = x->l; //Right child of root become left child of temp node
        x->l = h; //Left child of temp node become root
        h = x; //Root become temp node
    }
    //Insert keeping the tree balanced
    void insert_rootR(link& h, Item it) {
        if (!h) {
            h = new node(it);
            return;
        }
        if (h->item.key() < it.key()) {
            insert_rootR(h->r, it);
            rotL(h);
        }
        else {
            insert_rootR(h->l, it);
            rotR(h);
        }
    }
    Item selectR(link h, int k) {
          if (h == 0) return nullItem;
          int t = tree_size(h->l);
          if (t > k) return selectR(h->l, k);
          if (t < k) return selectR(h->r, k-t-1);  
          return h->item;
    }
    void partR(link& h, int k)
          {  int t = tree_size(h->l);
            if (t > k )
              { partR(h->l, k); rotR(h); }
            if (t < k )
              { partR(h->r, k-t-1); rotL(h); }
          } 
};

我的问题是...“ insert_rootR”是否始终保持树平衡? 还有……另一个问题是,“ selectR”和“ partR”如何工作? 谢谢!我希望我的问题有条理!

评论