Hướng dẫn recursive objects python - đối tượng đệ quy python

Các đối tượng có thể có các đối tượng khác là giá trị thuộc tính. Khi một đối tượng của một số lớp có giá trị thuộc tính của cùng một lớp, đó là một đối tượng đệ quy.

2.9.1 & nbsp; & nbsp; & nbsp; lớp danh sách được liên kết

Một danh sách được liên kết, được giới thiệu trước đó trong chương này, bao gồm một yếu tố đầu tiên và phần còn lại của danh sách. Phần còn lại của danh sách được liên kết tự nó là một danh sách được liên kết - & nbsp; một định nghĩa đệ quy. Danh sách trống là một trường hợp đặc biệt của một danh sách được liên kết không có phần tử đầu tiên hoặc phần còn lại. Danh sách được liên kết là một chuỗi: nó có độ dài hữu hạn và hỗ trợ lựa chọn phần tử theo chỉ mục.

Bây giờ chúng ta có thể thực hiện một lớp có hành vi tương tự. Trong phiên bản này, chúng tôi sẽ xác định hành vi của nó bằng cách sử dụng các tên phương thức đặc biệt cho phép lớp của chúng tôi hoạt động với trình vận hành Len Function và phần tử tích hợp (dấu ngoặc vuông hoặc toán tử.getItem) trong Python. Các hàm tích hợp này gọi các tên phương thức đặc biệt của một lớp: Độ dài được tính toán bởi __len__ và lựa chọn phần tử được tính toán bởi __getItem__. Danh sách liên kết trống được biểu thị bằng một tuple trống, có độ dài 0 và không có phần tử.

>>> class Link:
        """A linked list with a first element and the rest."""
        empty = ()
        def __init__(self, first, rest=empty):
            assert rest is Link.empty or isinstance(rest, Link)
            self.first = first
            self.rest = rest
        def __getitem__(self, i):
            if i == 0:
                return self.first
            else:
                return self.rest[i-1]
        def __len__(self):
            return 1 + len(self.rest)

>>> s = Link(3, Link(4, Link(5)))
>>> len(s)
3
>>> s[1]
4

Các định nghĩa của __len__ và __getItem__ trên thực tế là đệ quy. Hàm Python tích hợp Len gọi một phương thức gọi là __len__ khi được áp dụng cho đối số đối tượng do người dùng xác định. Tương tự như vậy, toán tử lựa chọn phần tử gọi một phương thức gọi là __getItem__. Do đó, các cơ quan của hai phương pháp này sẽ tự gọi mình là gián tiếp. Đối với __len__, trường hợp cơ sở đạt được khi self.rest đánh giá theo tuple trống, link.empty, có độ dài 0.

Hàm isinstance tích hợp trả về liệu đối số đầu tiên có loại hoặc kế thừa từ đối số thứ hai. ISInstance (REST, Link) là đúng nếu phần còn lại là một thể hiện liên kết hoặc một thể hiện của một số lớp liên kết.

Việc triển khai của chúng tôi đã hoàn tất, nhưng một ví dụ của lớp liên kết hiện rất khó kiểm tra. Để giúp gỡ lỗi, chúng tôi cũng có thể xác định một hàm để chuyển đổi liên kết thành biểu thức chuỗi.

>>> def link_expression(s):
        """Return a string that would evaluate to s."""
        if s.rest is Link.empty:
            rest = ''
        else:
            rest = ', ' + link_expression(s.rest)
        return 'Link({0}{1})'.format(s.first, rest)

>>> link_expression(s)
'Link(3, Link(4, Link(5)))'

Cách hiển thị một liên kết rất thuận tiện đến nỗi chúng tôi muốn sử dụng nó bất cứ khi nào một phiên bản liên kết được hiển thị. Chúng tôi có thể đảm bảo hành vi này bằng cách đặt hàm link_expression làm giá trị của thuộc tính lớp đặc biệt __repr__. Python hiển thị các phiên bản của các lớp do người dùng xác định bằng cách gọi phương thức __repr__ của họ.

>>> Link.__repr__ = link_expression
>>> s
Link(3, Link(4, Link(5)))

Lớp liên kết có thuộc tính đóng. Giống như một yếu tố của danh sách có thể là một danh sách, một liên kết có thể chứa một liên kết làm yếu tố đầu tiên của nó.

>>> s_first = Link(s, Link(6))
>>> s_first
Link(Link(3, Link(4, Link(5))), Link(6))

Danh sách liên kết S_FIRST chỉ có hai yếu tố, nhưng phần tử đầu tiên của nó là một danh sách được liên kết với ba yếu tố.

>>> len(s_first)
2
>>> len(s_first[0])
3
>>> s_first[0][2]
5

Các chức năng đệ quy đặc biệt phù hợp để thao tác các danh sách được liên kết. Chẳng hạn, hàm Extend_link đệ quy xây dựng một danh sách được liên kết có chứa các phần tử của một phiên bản liên kết S theo sau là các phần tử của một phiên bản liên kết khác t. Cài đặt chức năng này như phương thức __Add__ của lớp liên kết mô phỏng hành vi bổ sung của một danh sách tích hợp.

>>> def extend_link(s, t):
        if s is Link.empty:
            return t
        else:
            return Link(s.first, extend_link(s.rest, t))
>>> extend_link(s, s)
Link(3, Link(4, Link(5, Link(3, Link(4, Link(5))))))
>>> Link.__add__ = extend_link
>>> s + s
Link(3, Link(4, Link(5, Link(3, Link(4, Link(5))))))

Thay vì liệt kê danh sách, một danh sách được liên kết có thể được tạo từ một danh sách khác bằng cách sử dụng hai hàm bậc cao hơn: MAP_LINK và FILFLE_LINK. Hàm MAP_Link được xác định bên dưới áp dụng hàm F cho từng phần tử của danh sách được liên kết và xây dựng danh sách được liên kết có chứa kết quả.

>>> def map_link(f, s):
        if s is Link.empty:
            return s
        else:
            return Link(f(s.first), map_link(f, s.rest))
>>> map_link(square, s)
Link(9, Link(16, Link(25)))

Hàm Filter_link trả về một danh sách được liên kết chứa tất cả các phần tử của danh sách được liên kết s mà F trả về một giá trị thực. Sự kết hợp giữa MAP_LINK và FILFLE_LINK có thể diễn đạt cùng logic như một sự hiểu biết danh sách.

>>> def filter_link(f, s):
        if s is Link.empty:
            return s
        else:
            filtered = filter_link(f, s.rest)
            if f(s.first):
                return Link(s.first, filtered)
            else:
                return filtered
>>> odd = lambda x: x % 2 == 1
>>> map_link(square, filter_link(odd, s))
Link(9, Link(25))
>>> [square(x) for x in [3, 4, 5] if odd(x)]
[9, 25]

Hàm tham gia_link xây dựng đệ quy một chuỗi chứa các phần tử của danh sách được liên kết được tách biệt bởi một số chuỗi phân tách. Kết quả nhỏ gọn hơn nhiều so với đầu ra của Link_Expression.

>>> s = Link(3, Link(4, Link(5)))
>>> len(s)
3
>>> s[1]
4

0

Xây dựng đệ quy. Danh sách được liên kết đặc biệt hữu ích khi xây dựng trình tự tăng dần, một tình huống phát sinh thường xuyên trong các tính toán đệ quy. Linked lists are particularly useful when constructing sequences incrementally, a situation that arises often in recursive computations.

Chức năng Count_Partitions từ Chương 1 đã đếm số cách để phân vùng số nguyên n bằng cách sử dụng các phần lên đến kích thước m thông qua quy trình tái tạo cây. Với các chuỗi, chúng ta cũng có thể liệt kê các phân vùng này một cách rõ ràng bằng cách sử dụng một quy trình tương tự.

Chúng tôi theo cùng một phân tích đệ quy tương tự về vấn đề như chúng tôi đã làm trong khi đếm: phân vùng n sử dụng số nguyên lên đến m liên quan đến

1. phân vùng N-M bằng cách sử dụng số nguyên lên đến M, hoặcn-m using integers up to m, or
2. Phân vùng N sử dụng số nguyên lên đến M-1.m-1.

Đối với các trường hợp cơ sở, chúng tôi thấy rằng 0 có phân vùng trống, trong khi phân vùng số nguyên âm hoặc sử dụng các bộ phận nhỏ hơn 1 là không thể.

>>> s = Link(3, Link(4, Link(5)))
>>> len(s)
3
>>> s[1]
4

1

Trong trường hợp đệ quy, chúng tôi xây dựng hai nhóm phụ của các phân vùng. Đầu tiên sử dụng m, và do đó chúng tôi thêm m vào mỗi phần tử của kết quả sử dụng_m để tạo thành với_m.

Kết quả của các phân vùng được lồng rất nhiều: một danh sách được liên kết các danh sách được liên kết. Sử dụng Join_Link với các dấu phân cách thích hợp, chúng ta có thể hiển thị các phân vùng theo cách có thể đọc được của con người.

>>> s = Link(3, Link(4, Link(5)))
>>> len(s)
3
>>> s[1]
4

2

>>> s = Link(3, Link(4, Link(5)))
>>> len(s)
3
>>> s[1]
4

3

2.9.2 & nbsp; & nbsp; & nbsp; lớp cây

Cây cũng có thể được biểu diễn bằng các trường hợp của các lớp do người dùng xác định, thay vì các trường hợp lồng nhau của các loại trình tự tích hợp. Một cây là bất kỳ cấu trúc dữ liệu nào có thuộc tính một chuỗi các nhánh cũng là cây.

Giá trị bên trong. Trước đây, chúng tôi đã xác định các cây theo cách mà tất cả các giá trị xuất hiện ở lá cây. Nó cũng phổ biến để xác định các cây có giá trị bên trong ở rễ của mỗi cây con. Một giá trị bên trong được gọi là một nhãn trong cây. Lớp cây dưới đây đại diện cho những cây như vậy, trong đó mỗi cây có một chuỗi các nhánh cũng là cây. Previously, we defined trees in such a way that all values appeared at the leaves of the tree. It is also common to define trees that have internal values at the roots of each subtree. An internal value is called an label in the tree. The Tree class below represents such trees, in which each tree has a sequence of branches that are also trees.

>>> s = Link(3, Link(4, Link(5)))
>>> len(s)
3
>>> s[1]
4

4

Ví dụ, lớp cây có thể biểu thị các giá trị được tính toán trong một cây biểu thức để thực hiện FIB, hàm để tính toán các số Fibonacci. Hàm fib_tree (n) bên dưới trả về một cây có số fibonacci thứ n là nhãn của nó và một dấu vết của tất cả các số fibonacci được tính toán trước đó trong các nhánh của nó.

>>> s = Link(3, Link(4, Link(5)))
>>> len(s)
3
>>> s[1]
4

5

>>> s = Link(3, Link(4, Link(5)))
>>> len(s)
3
>>> s[1]
4

6

Cây được thể hiện theo cách này cũng được xử lý bằng cách sử dụng các hàm đệ quy. Ví dụ, chúng ta có thể tổng hợp các nhãn của một cây. Như một trường hợp cơ sở, chúng tôi trả lại rằng một nhánh trống không có nhãn.

>>> s = Link(3, Link(4, Link(5)))
>>> len(s)
3
>>> s[1]
4

7

>>> s = Link(3, Link(4, Link(5)))
>>> len(s)
3
>>> s[1]
4

8

Chúng ta cũng có thể áp dụng bản ghi nhớ để xây dựng cây Fibonacci, trong đó các cây con được lặp đi lặp lại chỉ được tạo một lần bởi phiên bản ghi nhớ của FIB_TREE, nhưng được sử dụng nhiều lần như các nhánh của các cây lớn hơn khác nhau.

>>> s = Link(3, Link(4, Link(5)))
>>> len(s)
3
>>> s[1]
4

9

Lượng thời gian tính toán và bộ nhớ được lưu bằng cách ghi nhớ trong những trường hợp này là đáng kể. Thay vì tạo 18.454.929 trường hợp khác nhau của lớp cây, giờ đây chúng tôi chỉ tạo ra 35.

2.9.3   Sets

Ngoài danh sách, tuple và từ điển, Python còn có loại container tích hợp thứ tư được gọi là một bộ. Đặt chữ theo ký hiệu toán học của các yếu tố được đặt trong niềng răng. Các yếu tố trùng lặp được loại bỏ khi xây dựng. Các bộ là các bộ sưu tập không theo thứ tự, và do đó, thứ tự được in có thể khác với thứ tự phần tử theo nghĩa đen.

>>> def link_expression(s):
        """Return a string that would evaluate to s."""
        if s.rest is Link.empty:
            rest = ''
        else:
            rest = ', ' + link_expression(s.rest)
        return 'Link({0}{1})'.format(s.first, rest)

0

Python SETS hỗ trợ nhiều hoạt động khác nhau, bao gồm các bài kiểm tra thành viên, tính toán độ dài và các hoạt động tập hợp tiêu chuẩn của Liên minh và Giao lộ

>>> def link_expression(s):
        """Return a string that would evaluate to s."""
        if s.rest is Link.empty:
            rest = ''
        else:
            rest = ', ' + link_expression(s.rest)
        return 'Link({0}{1})'.format(s.first, rest)

1

Ngoài Liên minh và Giao lộ, Python đặt ra hỗ trợ một số phương pháp khác. Các vị từ ISDISJOINT, ISSUBSET và phát hành cung cấp so sánh thiết lập. Các bộ có thể thay đổi và có thể được thay đổi một phần tử tại một thời điểm bằng cách sử dụng thêm, loại bỏ, loại bỏ và pop. Các phương pháp bổ sung cung cấp các đột biến đa yếu tố, chẳng hạn như rõ ràng và cập nhật. Tài liệu Python cho các bộ phải đủ dễ hiểu tại thời điểm này của khóa học để điền vào các chi tiết.

Thực hiện các bộ. Tóm tắt, một bộ là một tập hợp các đối tượng riêng biệt hỗ trợ thử nghiệm thành viên, liên minh, giao lộ và điều chỉnh. Tiếp cận một phần tử và một tập hợp trả về một bộ mới chứa tất cả các phần tử của bộ gốc cùng với phần tử mới, nếu nó khác biệt. Liên minh và giao lộ trả về tập hợp các phần tử xuất hiện trong cả hai hoặc cả hai bộ, tương ứng. Như với bất kỳ sự trừu tượng hóa dữ liệu nào, chúng tôi có thể tự do thực hiện bất kỳ chức năng nào đối với bất kỳ biểu diễn nào của các bộ cung cấp bộ sưu tập các hành vi này. Abstractly, a set is a collection of distinct objects that supports membership testing, union, intersection, and adjunction. Adjoining an element and a set returns a new set that contains all of the original set's elements along with the new element, if it is distinct. Union and intersection return the set of elements that appear in either or both sets, respectively. As with any data abstraction, we are free to implement any functions over any representation of sets that provides this collection of behaviors.

Trong phần còn lại của phần này, chúng tôi xem xét ba phương pháp thực hiện khác nhau khác nhau trong đại diện của chúng. Chúng tôi sẽ mô tả hiệu quả của các biểu diễn khác nhau này bằng cách phân tích thứ tự tăng trưởng của các hoạt động đã thiết lập. Chúng tôi sẽ sử dụng các lớp liên kết và cây của chúng tôi từ trước đó trong phần này, cho phép các giải pháp đệ quy đơn giản và thanh lịch cho các hoạt động tập cơ bản.

Đặt như các chuỗi không theo thứ tự. Một cách để biểu diễn một tập hợp là một chuỗi trong đó không có phần tử nào xuất hiện nhiều hơn một lần. Các tập trống được biểu thị bằng chuỗi trống. Kiểm tra thành viên đi bộ đệ quy thông qua danh sách. One way to represent a set is as a sequence in which no element appears more than once. The empty set is represented by the empty sequence. Membership testing walks recursively through the list.

>>> def link_expression(s):
        """Return a string that would evaluate to s."""
        if s.rest is Link.empty:
            rest = ''
        else:
            rest = ', ' + link_expression(s.rest)
        return 'Link({0}{1})'.format(s.first, rest)

2

>>> def link_expression(s):
        """Return a string that would evaluate to s."""
        if s.rest is Link.empty:
            rest = ''
        else:
            rest = ', ' + link_expression(s.rest)
        return 'Link({0}{1})'.format(s.first, rest)

3

>>> def link_expression(s):
        """Return a string that would evaluate to s."""
        if s.rest is Link.empty:
            rest = ''
        else:
            rest = ', ' + link_expression(s.rest)
        return 'Link({0}{1})'.format(s.first, rest)

4

Việc triển khai SET_Contains này yêu cầu trung bình $ \ theta (n) $ để kiểm tra thành viên của một yếu tố, trong đó $ n $ là kích thước của tập s. Sử dụng chức năng thời gian tuyến tính này để thành viên, chúng ta có thể liền kề một phần tử vào một tập hợp, cũng trong thời gian tuyến tính.$\Theta(n)$ time on average to test membership of an element, where $n$ is the size of the set s. Using this linear-time function for membership, we can adjoin an element to a set, also in linear time.

>>> def link_expression(s):
        """Return a string that would evaluate to s."""
        if s.rest is Link.empty:
            rest = ''
        else:
            rest = ', ' + link_expression(s.rest)
        return 'Link({0}{1})'.format(s.first, rest)

5

>>> def link_expression(s):
        """Return a string that would evaluate to s."""
        if s.rest is Link.empty:
            rest = ''
        else:
            rest = ', ' + link_expression(s.rest)
        return 'Link({0}{1})'.format(s.first, rest)

6

Trong việc thiết kế một đại diện, một trong những vấn đề mà chúng ta nên quan tâm là hiệu quả. C đến hai bộ SET1 và SET2 cũng yêu cầu thử nghiệm thành viên, nhưng lần này, mỗi yếu tố của SET1 phải được kiểm tra để thành viên trong SET2, dẫn đến thứ tự tăng trưởng bậc hai trong số các bước, $ \ theta (n^2) Hai bộ kích thước $ n $.$\Theta(n^2)$, for two sets of size $n$.

>>> def link_expression(s):
        """Return a string that would evaluate to s."""
        if s.rest is Link.empty:
            rest = ''
        else:
            rest = ', ' + link_expression(s.rest)
        return 'Link({0}{1})'.format(s.first, rest)

7

>>> def link_expression(s):
        """Return a string that would evaluate to s."""
        if s.rest is Link.empty:
            rest = ''
        else:
            rest = ', ' + link_expression(s.rest)
        return 'Link({0}{1})'.format(s.first, rest)

8

Khi tính toán liên minh của hai bộ, chúng ta phải cẩn thận không bao gồm bất kỳ yếu tố nào hai lần. Hàm union_set cũng yêu cầu một số thử nghiệm thành viên tuyến tính, tạo ra một quy trình cũng bao gồm các bước $ \ theta (n^2) $.$\Theta(n^2)$ steps.

>>> def link_expression(s):
        """Return a string that would evaluate to s."""
        if s.rest is Link.empty:
            rest = ''
        else:
            rest = ', ' + link_expression(s.rest)
        return 'Link({0}{1})'.format(s.first, rest)

9

>>> link_expression(s)
'Link(3, Link(4, Link(5)))'

0

Sets as ordered sequences. One way to speed up our set operations is to change the representation so that the set elements are listed in increasing order. To do this, we need some way to compare two objects so that we can say which is bigger. In Python, many different types of objects can be compared using < and > operators, but we will concentrate on numbers in this example. We will represent a set of numbers by listing its elements in increasing order.

Một lợi thế của việc đặt hàng hiển thị trong set_contains: Khi kiểm tra sự hiện diện của một đối tượng, chúng tôi không còn phải quét toàn bộ tập hợp. Nếu chúng ta đạt được một phần tử tập hợp lớn hơn mục chúng ta đang tìm kiếm, thì chúng ta biết rằng mục không có trong tập hợp:

>>> link_expression(s)
'Link(3, Link(4, Link(5)))'

1

>>> link_expression(s)
'Link(3, Link(4, Link(5)))'

2

Điều này tiết kiệm bao nhiêu bước? Trong trường hợp xấu nhất, mục chúng tôi đang tìm kiếm có thể là thứ lớn nhất trong bộ, vì vậy số bước giống như đối với đại diện không có thứ tự. Mặt khác, nếu chúng ta tìm kiếm các mục có nhiều kích thước khác nhau, chúng ta có thể mong đợi rằng đôi khi chúng ta sẽ có thể ngừng tìm kiếm tại một điểm gần đầu danh sách và những lần khác chúng ta vẫn sẽ cần kiểm tra hầu hết danh sách. Trung bình chúng ta nên mong đợi phải kiểm tra khoảng một nửa các mục trong bộ. Do đó, số bước trung bình cần thiết sẽ là khoảng $ \ frac {n} {2} $. Đây vẫn là $ \ theta (n) $ tăng trưởng, nhưng nó giúp chúng tôi tiết kiệm một thời gian trong thực tế so với triển khai trước đó.$\frac{n}{2}$. This is still $\Theta(n)$ growth, but it does save us some time in practice over the previous implementation.

Chúng ta có thể có được tốc độ tăng tốc ấn tượng hơn bằng cách thực hiện lại Intersect_set. Trong biểu diễn không được đặt hàng, thao tác này yêu cầu $ \ theta (n^2) $ các bước vì chúng tôi đã thực hiện quét hoàn toàn SET2 cho mỗi phần tử của SET1. Nhưng với biểu diễn được đặt hàng, chúng ta có thể sử dụng một phương pháp thông minh hơn. Chúng tôi lặp lại thông qua cả hai bộ đồng thời, theo dõi một phần tử E1 trong SET1 và E2 trong SET2. Khi E1 và E2 bằng nhau, chúng tôi bao gồm phần tử đó trong giao điểm.$\Theta(n^2)$ steps because we performed a complete scan of set2 for each element of set1. But with the ordered representation, we can use a more clever method. We iterate through both sets simultaneously, tracking an element e1 in set1 and e2 in set2. When e1 and e2 are equal, we include that element in the intersection.

Giả sử, tuy nhiên, E1 nhỏ hơn E2. Vì E2 nhỏ hơn các yếu tố còn lại của SET2, chúng tôi có thể kết luận ngay rằng E1 không thể xuất hiện ở bất cứ đâu trong phần còn lại của SET2 và do đó không ở trong giao điểm. Vì vậy, chúng tôi không còn cần phải xem xét E1; Chúng tôi loại bỏ nó và tiến hành phần tử tiếp theo của SET1. Logic tương tự tiến bộ thông qua các yếu tố của SET2 khi E2

>>> link_expression(s)
'Link(3, Link(4, Link(5)))'

3

>>> link_expression(s)
'Link(3, Link(4, Link(5)))'

4

Để ước tính số bước theo yêu cầu của quy trình này, hãy quan sát rằng trong mỗi bước, chúng tôi thu nhỏ kích thước của ít nhất một trong các bộ. Do đó, số lượng các bước cần thiết là nhiều nhất là tổng của các kích thước của SET1 và SET2, thay vì sản phẩm của các kích thước, như với biểu diễn không được đặt hàng. Đây là $ \ theta (n) $ tăng trưởng thay vì $ \ theta (n^2) $ - một tốc độ tăng tốc đáng kể, ngay cả đối với các bộ có kích thước vừa phải. Ví dụ, giao điểm của hai bộ kích thước 100 sẽ thực hiện khoảng 200 bước, thay vì 10.000 cho đại diện không có thứ tự.$\Theta(n)$ growth rather than $\Theta(n^2)$ -- a considerable speedup, even for sets of moderate size. For example, the intersection of two sets of size 100 will take around 200 steps, rather than 10,000 for the unordered representation.

Điều chỉnh và liên minh cho các bộ được biểu diễn dưới dạng trình tự được đặt hàng cũng có thể được tính toán trong thời gian tuyến tính. Những triển khai này được để lại như một bài tập.

Bộ như cây tìm kiếm nhị phân. Chúng ta có thể làm tốt hơn so với biểu diễn danh sách theo thứ tự bằng cách sắp xếp các phần tử đã đặt dưới dạng cây có chính xác hai nhánh. Mục nhập của gốc của cây chứa một phần tử của tập hợp. Các mục trong nhánh bên trái bao gồm tất cả các yếu tố nhỏ hơn so với gốc. Các mục trong nhánh bên phải bao gồm tất cả các yếu tố lớn hơn một trong số gốc. Hình dưới đây cho thấy một số cây đại diện cho bộ {1, 3, 5, 7, 9, 11}. Cùng một tập hợp có thể được biểu diễn bởi một cây theo một số cách khác nhau. Trong tất cả các cây tìm kiếm nhị phân, tất cả các yếu tố ở nhánh bên trái đều nhỏ hơn mục nhập ở gốc và tất cả các phần tử trong cây con bên phải đều lớn hơn. We can do better than the ordered-list representation by arranging the set elements in the form of a tree with exactly two branches. The entry of the root of the tree holds one element of the set. The entries within the left branch include all elements smaller than the one at the root. Entries in the right branch include all elements greater than the one at the root. The figure below shows some trees that represent the set {1, 3, 5, 7, 9, 11}. The same set may be represented by a tree in a number of different ways. In all binary search trees, all elements in the left branch be smaller than the entry at the root, and that all elements in the right subtree be larger.

Ưu điểm của biểu diễn cây là thế này: Giả sử chúng ta muốn kiểm tra xem giá trị V có chứa trong một tập hợp hay không. Chúng tôi bắt đầu bằng cách so sánh V với mục nhập. Nếu V nhỏ hơn thế này, chúng ta biết rằng chúng ta chỉ cần tìm kiếm cây con bên trái; Nếu V lớn hơn, chúng ta chỉ cần tìm kiếm cây con phù hợp. Bây giờ, nếu cây "cân bằng", mỗi cây con này sẽ có kích thước khoảng một nửa so với bản gốc. Do đó, trong một bước, chúng tôi đã giảm vấn đề tìm kiếm một cây có kích thước $ n $ để tìm kiếm một cây có kích thước $ \ frac {n} {2} $. Vì kích thước của cây được giảm một nửa ở mỗi bước, chúng ta nên mong đợi rằng số bước cần thiết để tìm kiếm một cây phát triển là $ \ theta (\ log n) $. Đối với các bộ lớn, đây sẽ là một tốc độ tăng tốc đáng kể so với các biểu diễn trước đó. Hàm set_contains này khai thác cấu trúc thứ tự của bộ có cấu trúc cây.$n$ to searching a tree of size $\frac{n}{2}$. Since the size of the tree is halved at each step, we should expect that the number of steps needed to search a tree grows as $\Theta(\log n)$. For large sets, this will be a significant speedup over the previous representations. This set_contains function exploits the ordering structure of the tree-structured set.

>>> link_expression(s)
'Link(3, Link(4, Link(5)))'

5

Tiếp cận một mục vào một tập hợp được thực hiện tương tự và cũng yêu cầu $ \ theta (\ log n) $ các bước. Để liền kề với giá trị V, chúng tôi so sánh V với mục nhập để xác định xem V nên được thêm vào bên phải hay vào nhánh bên trái và đã liền kề v với nhánh thích hợp, chúng tôi đặt nhánh mới được xây dựng cùng với mục nhập gốc và nhánh khác . Nếu V bằng với mục nhập, chúng tôi chỉ trả lại nút. Nếu chúng tôi được yêu cầu liền kề V đến một cây trống, chúng tôi sẽ tạo ra một cây có V như là lối vào và các nhánh bên phải và trái. Đây là chức năng:$\Theta(\log n)$ steps. To adjoin a value v, we compare v with entry to determine whether v should be added to the right or to the left branch, and having adjoined v to the appropriate branch we piece this newly constructed branch together with the original entry and the other branch. If v is equal to the entry, we just return the node. If we are asked to adjoin v to an empty tree, we generate a Tree that has v as the entry and empty right and left branches. Here is the function:

>>> link_expression(s)
'Link(3, Link(4, Link(5)))'

6

>>> link_expression(s)
'Link(3, Link(4, Link(5)))'

7

Yêu cầu của chúng tôi rằng việc tìm kiếm cây có thể được thực hiện trong một số bước logarit dựa trên giả định rằng cây được "cân bằng", tức là, phần cây bên trái và bên phải của mỗi cây có cùng một số phần tử, để mỗi phần tử Subtree chứa khoảng một nửa các yếu tố của cha mẹ của nó. Nhưng làm thế nào chúng ta có thể chắc chắn rằng những cây chúng ta xây dựng sẽ được cân bằng? Ngay cả khi chúng ta bắt đầu với một cây cân bằng, việc thêm các phần tử với liền kề có thể tạo ra kết quả không cân bằng. Vì vị trí của một phần tử mới liền kề phụ thuộc vào cách phần tử so sánh với các mục đã có trong tập hợp, chúng ta có thể mong đợi rằng nếu chúng ta thêm các phần tử "ngẫu nhiên", cây sẽ có xu hướng được cân bằng trung bình.

Nhưng đây không phải là một sự đảm bảo. Ví dụ: nếu chúng ta bắt đầu với một bộ trống và liền kề các số từ 1 đến 7 theo trình tự, chúng ta kết thúc với một cây không cân bằng cao, trong đó tất cả các cây con bên trái đều trống, vì vậy nó không có lợi thế so với một danh sách đơn giản. Một cách để giải quyết vấn đề này là xác định một hoạt động biến đổi một cây tùy ý thành một cây cân bằng với các yếu tố tương tự. Chúng tôi có thể thực hiện chuyển đổi này sau mỗi vài hoạt động liền kề để giữ cho SET của chúng tôi cân bằng.

Các hoạt động giao nhau và công đoàn có thể được thực hiện trên các bộ có cấu trúc cây trong thời gian tuyến tính bằng cách chuyển đổi chúng thành danh sách được đặt hàng và trở lại. Các chi tiết được để lại như một bài tập.

Python đặt thực hiện. Loại tập hợp được tích hợp vào Python không sử dụng bất kỳ biểu diễn nào trong số này trong nội bộ. Thay vào đó, Python sử dụng một đại diện cung cấp các bài kiểm tra thành viên thời gian liên tục và các hoạt động liền kề dựa trên một kỹ thuật gọi là băm, đây là một chủ đề cho một khóa học khác. Các bộ Python tích hợp không thể chứa các loại dữ liệu có thể thay đổi, chẳng hạn như danh sách, từ điển hoặc các bộ khác. Để cho phép các bộ lồng nhau, Python cũng bao gồm một lớp Frozenset bất biến tích hợp, chia sẻ các phương thức với lớp đã đặt nhưng loại trừ các phương thức đột biến và toán tử. The set type that is built into Python does not use any of these representations internally. Instead, Python uses a representation that gives constant-time membership tests and adjoin operations based on a technique called hashing, which is a topic for another course. Built-in Python sets cannot contain mutable data types, such as lists, dictionaries, or other sets. To allow for nested sets, Python also includes a built-in immutable frozenset class that shares methods with the set class but excludes mutation methods and operators.