什么？排序树查找第k个元素平均时间复杂度可以为O（lgn）？|树

方案：查找树的基础上添加了一个元素，用来记录当前子树的元素个数。

//查找第k个元素转用数据结构
typedef struct BiNode_K{
    ElemType data;
    struct BiNode_K *lchild,*rchild;
    //存放的是包括其自身在内的子树的节点个数
    int NbrOfChild;
}BiNode_K,*BiTree_K;

//BST-插入
template <typename Node>
bool BST_Insert(Node **Tree,int Num)
{
    if ((*Tree)==NULL)
    {
        (*Tree) = (Node *)malloc(sizeof(Node));
        (*Tree)->data = Num;
        (*Tree)->lchild = (*Tree)->rchild = NULL;
        return true;
    }
    else if(Num<((*Tree)->data))
    {
        return BST_Insert(&((*Tree)->lchild),Num);
    }
    else if (Num>((*Tree)->data))
    {
        return BST_Insert(&((*Tree)->rchild),Num);
    }
    else
    {
        return false;
    }
}

//BST-建立
template <typename TreePtr>
bool BST_Bulid(TreePtr Tree,ElemType Buff[],int len)
{
    int ErrorCnt=0;

    for (int i=0;i<len;i++)
    {
        if (!BST_Insert(Tree,Buff[i]))
        {
            ErrorCnt++;
        }
    }

    if (ErrorCnt>0)
    {
        return false;
    } 
    else
    {
        return true;
    }
}
//递归统计每个节点孩子个数
int CreateKTree1(BiTree_K Tree)
{
    if (Tree==NULL)
    {
        return 0;
    }

    return  Tree->NbrOfChild = CreateKTree1(Tree->lchild) + CreateKTree1(Tree->rchild) + 1;
}

//创建查找第k个元素的排序树
void CreateKTree(BiTree_K *Tree, ElemType Buff[],int len)
{
    BST_Bulid(Tree,Buff,len);

    CreateKTree1(*Tree);
}

//查找第k个数字
//返回0表示k超出范围
ElemType KTreeFindKthNum(BiTree_K Tree,int k)
{
    int NbrOfLeftChild = 0,NbrOfRightChild = 0;

    if (Tree==NULL)
    {
        return 0;
    }

    if ((Tree->NbrOfChild)<k)
    {
        return 0;
    }

    if (Tree->lchild!=NULL)
    {
        NbrOfLeftChild = Tree->lchild->NbrOfChild;
    }

    if (Tree->rchild!=NULL)
    {
        NbrOfRightChild = Tree->rchild->NbrOfChild;
    }

    //要查找的数字在左孩子里面
    if (k<=NbrOfLeftChild)
    {
        KTreeFindKthNum(Tree->lchild,k);
    }
    else if (k==(NbrOfLeftChild+1))
    {
        return Tree->data;
    }
    else
    {
        return KTreeFindKthNum(Tree->rchild,k - NbrOfLeftChild - 1);
    }
}

python实现：

# 节点记录了子树的节点个数
# 此树的优点在于可以二分法查找第k小的节点，平均时间复杂度为O(logn)，普通或者平衡二叉树都做不到！
class MySearchTreeWithCount(MySearchTree):
    # def __init__(self,data):
    #     if type(data) is list:
    #         if len(data) < 2:
    #             self.root = None
    #             return
    #
    #     self.root = Node(data[1])
    #
    #     root = self.root
    #     for elem in data[2:]:
    #         self.insert_node(root,elem)

    # 重载

    def insert_node(self, root, elem):
        root.node_count += 1
        if elem <= root.data:
            if root.lc:
                self.insert_node(root.lc, elem)
            else:
                root.lc = Node(elem)
        else:
            if root.rc:
                self.insert_node(root.rc, elem)
            else:
                root.rc = Node(elem)

    def find_kth_elem(self,root,k):
        # k: 1~n
        if k > root.node_count or k <= 0:
            return None

        lc_num = root.lc.node_count if root.lc else 0

        if k <= lc_num:
            return self.find_kth_elem(root.lc)
        elif lc_num == (k-1):
            return root.data
        else:
            return self.find_kth_elem(root.rc,k - lc_num - 1)