خم مرتبه زد
ساختن چهاردرخت به‌طور مؤثر

از مرتب‌سازی Z می‌توان برای ساختن یک چاردرخت برای مجموعه‌ای از نقاط استفاده کرد. ایدهٔ اصلی این است که مجموعهٔ ورودی را مطابق مرتبه Z مرتب کنید. پس از مرتب‌سازی، نقاط هم می‌توانند در یک درخت دودویی جستجوی ذخیره شوند و به‌طور مستقیم استفاده شوند، که به آن چاردرخت خطی گفته می‌شود، و هم می‌توانند برای ساخت یک چاردرخت مبتنی بر پوینتر استفاده شوند.
نقاط ورودی معمولاً در هر بعدی به صورت اعداد صحیح مثبت هستند، چه به عنوان یک نقطه ثابت در محدوده [۰ ، ۱] و چه متناسب با طول کلمه دستگاه. هر دو نمایش معادل هستند و اجازه می‌دهند بالاترین مرتبه بیت غیر صفر در زمان ثابت یافت شود. هر مربع در چاردرخت دارای طول ضلع است که توان آن دو است و مختصات گوشه که مضرب طول ضلع است. با توجه به هر دو نقطه، مربع بدست آمده برای دو نقطه، کوچکترین مربع است که هر دو نقطه را پوشش می‌دهد. به مخلوط کردن بیت‌های مؤلفه‌های x و y هر نقطه، شافل (shuffle) نقاط x و y گفته می‌شود و می‌تواند برای ابعاد بالاتر هم تعمیم پیدا کند.
نقاط را می‌توان با توجه به شافل آن‌ها طبقه‌بندی کرد بدون اینکه صریحاً بیت‌ها در هم آمیخته شود. برای انجام این کار، برای هر بعد، چپ‌ترین بیت از XOR مختصات دو نقطه، برای آن بعد مورد بررسی قرار می‌گیرد. بعدی که بیت سمت چپ آن از بقیه بزرگتر است برای مقایسه دو نقطه برای تعیین ترتیب شافل آن‌ها استفاده می‌شود.
عملیات XOR بیت‌های مرتبه بالاتر که در آن‌ها دو مختصات یکسان هستند را تعیین می‌کند. از آنجا که شافل، بیت‌ها را از مرتبه بالاتر به مرتبه پایین‌تر به هم می‌ریزد، مختصات با بزرگترین بیت سمت چپ را اینگونه شناسایی می‌کند که ابتدا اولین بیت در ترتیب شافل که متفاوت است را شناسایی می‌کند و از این مختصات برای مقایسه دو نقطه استفاده می‌کند. کد پایتون این عملیات به صورت زیر است:
def cmp_zorder(lhs, rhs):
        # assume lhs and rhs array-like objects of indices
        assert len(lhs) == len(rhs)
        # will contain the most significant dimension
        msd = 0
        # loop over the other dimensions
        for dim in range(1, len(lhs)):
            # check if the current dimension is more significant
            # by comparing the most significant bits
            if less_msb(lhs[msd] ^ rhs[msd], lhs[dim] ^ rhs[dim]):
                msd = dim
        return lhs[msd] <rhs[msd]
یک راه برای تعیین اینکه آیا بیت سمت چپ کوچکتر است، مقایسه کف لگاریتم پایه-۲ هر نقطه است. عملیات زیر معادل است و فقط به عملیات xor نیاز دارد:
def less_msb(x, y):
        return x <y and x <(x ^ y)
همچنین می‌توان اعداد ممیز شناور را با استفاده از همین تکنیک مقایسه کرد. تابع less_msb ابتدا اکسپوننت‌ها (قسمت توان اعداد شناور) را مقایسه می‌کند. فقط وقتی مساوی باشند، تابع less_msb روی مانتیساها (قسمت عدد اعداد شناور) اعمال می‌شود.
هنگامی که امتیازها مرتب شدند، دو ویژگی باعث می‌شود که یک چاردرخت آسان ساخته شود: اولین نکته این است که نقاط موجود در یک مربع چاردرخت، به صورت مرتب شده و با فاصلهٔ متناوب باشند. دوم اینکه اگر بیش از یک بچهٔ مربع دارای یک نقطه ورودی باشد، مربع از دو نقطهٔ مرتب شدهٔ مجاور نشات گرفته شده‌است.
برای هر دو نقطهٔ مجاور، مربع بدست آمده محاسبه می‌شود و طول آن مشخص می‌شود و برای هر مربع بدست آمده، فاصلهٔ شامل آن مربع توسط اولین مربع بزرگتر سمت راست و اولین مربع بزرگتر سمت چپ که به صورت مرتب شده هستند بدست می‌آید. هر کدام از این فاصله‌ها با مربع چاردرخت مطابقت دارد. نتیجه این کار یک چاردرخت فشرده شده‌است، که در آن فقط گره‌های حاوی نقاط ورودی یا دو یا چند بچه در آن حضور دارند. در صورت تمایل می‌توانید با قرار دادن گره‌های از دست رفته یک چاردرخت غیر فشرده بسازید.
به جای ایجاد یک چاردرخت مبتنی بر پوینتر، نقاط را می‌توان به صورت مرتب شده در داده ساختاری مانند درخت جستجوی دودویی حفظ کرد. این کار به ما اجازه می‌دهد تا در زمان (O(log n نقاط را درج و حذف کنیم. دو چاردرخت را می‌توان با ادغام دو مجموعهٔ مرتب شده از نقاط، و از بین بردن تکراری‌ها ادغام کرد. جای نقاط را می‌توان با جستجوی نقاط قبل و دنبال کردن نقطهٔ پرسیده شده به ترتیب مرتب شده انجام داد. اگر چاردرخت فشرده شده باشد، گره قبلی پیدا شده ممکن است یک برگ دلخواه در داخل گره فشرده شدهٔ مورد نظر باشد. در این حالت، لازم است که اولین جد مشترک نقطه پرسیده شده و برگ پیدا شده را پیدا کنیم.