Python中使用常量额外空间计算 BST 中的第 K 大元素

二叉搜索树BST是一种二进制数据结构,包含具有一些属性的各种节点,包括:

  • 左子树节点小于根节点。
  • 右子树节点比根节点多。
  • 树节点的每个节点的子节点形成二叉搜索树。

问题陈述
我们需要找到现有二叉搜索树中的第 K 大元素。这意味着我们首先将二叉搜索树的元素按降序排列;然后,我们将从二叉搜索树中搜索第 k 大的元素。
让我们借助示例来理解问题陈述。

输入:

k = 4  
Binary Search Tree  
            Root Node  
              15  
            /      \  
         8         25  
        /              \  
      6                21  
     /                  /   \  
   13              14    18  

输出:
14

我们有一棵二叉搜索树,需要搜索第 K 个最大的元素。我们的输入为 4,即 k 为 4。我们需要从二叉搜索树中搜索第 4 大元素。我们首先将二叉搜索树中的元素按降序排列,然后找出第 4 大元素。

在 BST 中查找第 K 大元素的方法
在 BST 中查找第 k 个元素有不同的方法。这包括:
1. 幼稚的方法
使用朴素的方法,我们可以存储中序遍历,然后我们将找到n - k + 1 个元素,其中 n 是元素的数量,k 是我们需要搜索的元素。这种方法的空间复杂度为O(N),这意味着它将占用更多空间并且效率低下。
因此,我们将使用更有效的方法来查找二叉搜索树中的第 K 大元素。

2. 逆莫里斯遍历
该方法基于线程二叉树。线程二叉树只是一个带有额外线程的普通二叉树,这有助于轻松遍历树。它使用NULL指针,它存储了后继和前驱(前一个和下一个节点),用于使用这些NULL指针未使用的内存。

逆向莫里斯遍历只是逆向莫里斯遍历。与莫里斯遍历不同,在莫里斯遍历中,我们首先移动到左子树,然后移动到右子树,而不使用堆栈或递归,在反向莫里斯遍历中,我们将首先遍历右子树,然后再遍历左子树。它消耗了恒定的 O(1) 额外内存。这是在二叉搜索树中查找第 k 大元素的最佳且最有效的方法。

此问题陈述的逻辑是执行反向中序遍历,默认情况下按降序排序给出列表,并跟踪访问的节点数。当该计数等于我们要搜索的元素 (k) 时,我们将打印该元素。

寻找二叉搜索树中第k大元素的实现

class new_Node:  
    def __init__(self, ele):  
        self.ele = ele  
        self.right = self.left = None  
   
def KthLargestElement(root, k):  
    current = root  
    Klargestele = None  
    cnt = 0       # count variable  
   
    while (current != None):  
           
        # checking if the right child is None  
        if (current.right == None):  
             # 增加计数,然后检查计数是否等于 k  ;
            cnt += 1  
            if (cnt == k):  
      # If it matches the current is the required element  
                Klargestele = current      
   
            # else move it to the left child  
            current = current.left  
   
        else:  
   
            # finding inorder successor  
            succ_node = current.right  
   
            while (succ_node.left != None and  
                   succ_node.left != current):  
                succ_node = succ_node.left  
   
            if (succ_node.left == None):  
          
                succ_node.left = current  
   
                # moving current to its right  
                current = current.right  
   
            # removing thread links and getting the binary tree  
            else:  
   
                succ_node.left = None  
                cnt += 1  
                if (cnt == k):  
                    Klargest = current  
   
                # moving current to its left child  
                current = current.left  
   
    return Klargestele  
   
if __name__ == '__main__':  
   
    root = new_Node(8)  
    root.left = new_Node(1)  
    root.right = new_Node(9)  
    root.left.left = new_Node(3)  
    root.left.right = new_Node(2)  
    root.right.left = new_Node(11)  
    root.right.right = new_Node(15)  
      
    pos=input("Enter the kth element to be searched: ")  
    print("The  K-th largest Node in Binary Search Tree is : ",  
           KthLargestElement(root, pos).ele)  

输出:
Enter the kth element to be searched: 3
The  K-th largest Node in Binary Search Tree is :  11

使用的二叉树是

我们首先将当前节点初始化为根节点。我们初始化了一个计数变量,以相反的顺序遍历二叉树,检查第 k 个元素是否与当前节点匹配,并计算节点数。我们发现第 11 个元素是第 k 个最大的元素(k = 3)。