2

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

 7 months ago
source link: https://www.jdon.com/72450.html
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
neoserver,ios ssh client

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）。


report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK