Episode 112: Trees

 Download

We are sponsored by audible! http://www.audibletrial.com/programmingthrowdown

We are on Patreon! https://www.patreon.com/programmingthrowdown

T-Shirts! http://www.cafepress.com/programmingthrowdown/13590693

Join us on Discord! https://discord.gg/r4V2zpC

Trees

In another duo episode, Jason and Patrick give an in-depth introduction to trees, their many types, approaches and functions, and their importance in modern programming. Also, peppered throughout the episode are the games, books, tools, and ideas that have currently piqued their interest.

This episode touches on the following key topics and ideas:

00:00:17 Avoiding drama at work

00:07:10 News: C++20 (7:10)

00:09:37 News: Play Co-op Diablo II in the browser

00:12:58 Wreckfest

00:15:07 Kaboom

00:17:45 The future of remote work

00:24:46 Jason’s Book of the Show: Debt: The First 5000 Years

00:27:08 fractional-reserve banking

00:31:30 DeFi, distributed finance

00:33:08 Patrick’s Book of the Show: Harry Potter and the Sorcerer's Stone, the Illustrated Edition

00:35:49 (Ad) Audible

00:37:05 Jason’s Tool of the Show: Vagrant

00:41:04 Patrick’s Tool of the Show: Zach Gage Games

00:45:03 (Ad) ConfigCat

00:46:03 feature flags

00:47:03 Trees: why are they important? 

00:49:43 The divide and conquer approach

00:51:34 The agglometric approach

00:55:57 Choosing the right tree and algorithm

00:57:56 Keeping trees balanced

01:01:10 binary trees

01:02:52 binary trees and machine learning

01:05:28 b-trees

01:10:04 spatial trees: the k-d tree

01:16:50 k-d trees and multidimension

01:18:42 quadtrees and octrees

01:21:44 r-trees

Resources mentioned in this episode:

Books

• Debt: The First 5000 Years, by David Graeber https://amzn.to/3uKEoe9

• Harry Potter and the Sorcerer's Stone, The Illustrated Edition, by JK Rowling https://amzn.to/2R6ILSs

Games

• Diablo II browser game http://clouddiablo.com/

• Wreckfest https://www.thqnordic.com/games/wreckfest

• Zach Gage Games http://stfj.net/

Tools

• Vagrant https://www.vagrantup.com/

• Kaboom https://replit.com/kaboom

Articles

• Article on C++20: https://oleksandrkvl.github.io/2021/04/02/cpp-20-overview.html

• The debate over remote work: https://www.bbc.com/news/technology-56771539

Get ConfigCat: https://configcat.com/

Get Audible: http://www.audibletrial.com/programmingthrowdown

If you’ve enjoyed this podcast, you can listen to more programming news and updates like this one on Programming Throwdown’s website: https://www.programmingthrowdown.com/

You can also follow Programming Throwdown on 

Facebook | Apple Podcasts | Spotify | Player.FM 

You can also help support Programming Throwdown through our Patreon.

Transcript:

Programming Throwdown Episode 109 - Trees

Patrick Wheeler: Programming Throwdown Episode 112: Trees. Take it away, Jason.

[00:00:21] Jason Gauci: Hey everybody. So, this is going to be a pretty cool episode. Another duo episode, as we talked about a little earlier. You know, we got some awesome folks, literally the company's called Awesome Pros. So check them out if you're interested for your podcast. But we got some awesome folks helping us out on the, you know, editing, recording side. So we're able to produce more content, which is super exciting.

[00:00:45] And, and we we've had a bunch of ideas. We have, we have a whole list of ideas lined up of stuff that we want to chat about. And today we're going to be talking about trees, computer trees, although there is that whole thing about planting a million trees. Have you heard about that?

[00:00:59] Patrick Wheeler: On YouTube? I thought, you know, that's funny. I thought the same thing. People are going to assume we're talking about fundraising for planting trees.

[00:01:05] Jason Gauci: Yeah. You know, honestly, I don't know very much about it. I mean, it sounds cool. Sounds like, you know, planting trees sounds like it's pretty universally, like a good thing to do, but no, this is about computer trees.

[00:01:17] Yeah. We're gonna, we're gonna dive really deep into that, but first of all, we'll talk a little bit about avoiding drama at work. So...

[00:01:24] Patrick Wheeler: Dramatic.

[00:01:25] Jason Gauci: You know (laugh) this, so there is, you know, a lot of sources of drama at work. There are, you know, political things. There are various sort of social situations or like, I dunno, social phenomena.

[00:01:39] I mean, there's also just, you know, other than the macro stuff, there's also just like what we call like office politics. You know, this person, you know, is in a bind, and they kind of backstabbed this other person. And then, you know, there's all of this drama and... I'm here to tell you to avoid the drama and we're to give some tips on how to avoid drama at work.

[00:01:59] You know, maybe we'll just ping pong back and forth. I mean, my biggest thing, my biggest piece of advice, that really like it's, it's actually, you kind of influence people just by being yourself. Right. And so you don't really have to go out of your way to tell people how you feel about things that are, like besides the work you're doing. Right?

[00:02:20] So, I mean, you know, just by being, you know, yourself and having opinions that you're proud of, you know, and all of that, you know, that that's kind of, in my opinion, that's kind of enough, right? I mean, you don't then have to like engage in like a whole bunch of these other discussions. And so when I see... and you might see a lot of things, this, this is true even in your public life, but especially in your professional life, like you might see a lot of things and then feel compelled to say, Oh, like, I want to argue with this, or I want to go back and forth, you know, on this, on this topic or this issue with this person at work.

[00:02:55] And it's really important to just kind of take a step back and say, you know, like, just remember that just your kind of presence and, you know, in the way that you kind of think about things is already being expressed just through you being yourself, you don't also have to kind of take the extra step.

[00:03:15] Patrick Wheeler: Yeah. I, I think I hear what you're saying. I think what you're saying is like, by, rather than explicitly having to state loudly, what you think or how you want something to be, what you're saying is like, over time, sort of being consistently acting in a manner, which is true to those things that you think, then, you kind of like express them into your work environment.

[00:03:37] Jason Gauci: Yeah, exactly. And another thing too is, you know, there was a situation a really long time ago where someone had done something that I felt was, was not, was not right. Now, of course, like if there is issues with, you know, harassment or anything like that, you know, of course you need to speak up. I mean, that is extremely important, but I'm just saying, I mean, this wasn't anything like that, but it's something where I kind of felt really compelled to kind of, you know, start, kind of a discussion that that was probably not going to be very productive.

[00:04:11] And I decided, you know, no, I don't really want to kind of get into this kind of stuff at work. And then actually, what ended up happening is this took a little bit of, it took a while. You know, it's not something happened overnight, but, but eventually that person, you know, ended up kind of losing a lot of their authority and their, and their seniority and things at work.

[00:04:34] And, and the thing I realized from that experience was. You know, at that moment, I felt like, you know, there was this kind of real attack on me personally. And then I had to stand up for myself. But then, you know, in hindsight it was obvious that, you know, this person kind of had a problem with everybody.

[00:04:53] It really had nothing to do with, to me. I was just one of the people that this person was interacting with. And, now there is sort of a tragedy of the commons. Like you could, you could say to yourself, well, if no one does anything, then this sort of toxic person might just continue being toxic forever.

[00:05:10] And so you do have to kind of balance that out, but at the same time, I think it's so easy to go the other way and kind of get into a really big battle that is, you know, ultimately just going to take a lot of your time and energy and resources and, we'll just not really be productive for anybody.

[00:05:27] Patrick Wheeler: This is going to come across sounding a lot like a self-help. (laugh)

[00:05:31] Jason Gauci: Well, I mean, I think it's, yeah, actually I saw a study that said, the number two reason why CEOs get fired is actually like public scandal, which, you know, the number one reason is performance. So I mean, that's kind of a no brainer, right? People get fired for performance, especially at that high of a level. But you know, the number two reason is effectively, you know, some type of like public faux pas or something.

[00:05:56] And that's huge, when you think about all the other reasons someone could get fired. I mean, they could get fired for, like maybe they, they had some financial problem. Like they, they had a financial error and so like, you know, the SEC gets involved. There's all these other reasons why a CEO could get terminated, but that was number two. Right. And so, so yeah, I think it's a really poignant topic. And I guess the biggest thing is, is just to always just keep a level head and kind of keep your cool.

[00:06:25] And, especially, you know, at work, I think, I also don't really understand why people argue political stuff over the internet, but if you're going to do it at least do it over the internet, not at the water cooler or something.

[00:06:37] Patrick Wheeler: At least do it pseudo-anonymously and not in person.

[00:06:40] Jason Gauci: Yeah, exactly. (laugh) Yeah. All right.

[00:06:43] So that's, that's my rant about avoiding drama at work. It's so important and it takes a lot of, fortitude, but I think at the end, you're always going to look back and say, you know, I'm really proud of myself for having that kind of reserve. Right.

[00:06:57] Patrick Wheeler: Makes sense. Yeah. That's hard to follow up, man. I don't know. That was a, a heady opening topic.

[00:07:02] Jason Gauci: All right. (laugh) We'll jump into the news, then. The news is much more benign.

[00:07:07] Patrick Wheeler: Okay. No, good stuff. Good stuff. Yeah. A drama, ugh.

[00:07:10] My completely unrelated to drama is, my first link is C++20. New features with example, this article that I found shows almost all of the new C++20 core features, and gives a little like code snippet for how each of them works.

[00:07:26] Now, this is obviously like gonna make sense to a subset of the subset of a subset of our audience. (laugh) I always find this like, it's so useful because to me, I always, someone was showing, you know, recently we went to C++17 at work. And although, you know, that's an upgrade install a few years old, it takes a while for these things to kind of roll out if you're not familiar with C++, and someone was like listing off the new features.

[00:07:51] And all I'm doing is like, I don't even know what that means. Like, what was it? There was like the ternary operator. And I'm like, I don't even know what the, or the trigraph. We knew what the ternary operator is, but there's something like the trigraph operator has been deprecated in C++17. Like, I don't know what that is. Like,go look it up.

[00:08:08] Jason Gauci: Is that the thing with the question mark in the colon?

[00:08:11] Patrick Wheeler: That's the ternary operator, that one's still good.

[00:08:14] Jason Gauci: Okay.

[00:08:14] Patrick Wheeler: But there's a trigraph operator, which I forgot. I don't even remember what it is now. It's like question mark, angle, bracket, angle ,bracket, or something.

[00:08:21] Jason Gauci: What?

[00:08:21] Patrick Wheeler: And I (laugh) didn't even know it was a thing, which is why it's been deprecated.

[00:08:26] Anyways. So seeing all this, like this was super helpful for me to be able to realize like, what these named things actually meant, because I know it means something very specific and language is very important, and the C++ Standards Committee, I'm sure, worked very hard to make sure it makes sense, but it doesn't make sense to me.

[00:08:43] And so seeing the code examples allows me to quickly discount 90% of them as not useful to me. I mean, to understand, you know, what these new features are. I'm not a big fan of jumping in and using all of the new features, but it's definitely helpful to kind of see them written down.

[00:08:58] So I really appreciated this article. we'll have a link in the show notes because it's, on someone's get hub page and it's really long. So I'm not gonna say it out loud, but if you use C++, you're interested in seeing what new features are in 20, check out the show notes and definitely visit this link.

[00:09:13] Jason Gauci: What was the version that added lambdas? Thst was the last big feature.

[00:09:17] Patrick Wheeler: 13 or 11? I think 11.

[00:09:20] Jason Gauci: Oh, it's that old? Yeah. Lambdas, and then, well, actually one that came out, it might be in 20, or it might be in 20 where it's not experimental anymore is the file system library. That was another really important one

[00:09:30] Patrick Wheeler: Oh, 17. Yeah. Okay.

[00:09:32] Jason Gauci: Those are the two I remember where I was like, Oh, we totally needed this for such a long time.

[00:09:37] Cool. All right. My news is: Play Co-op Diablo II in the browser.

[00:09:42] So there's always this interesting, kind of, march towards, you know, doing just more and more exotic things in the browser. So this is, you know, I know a while back, Maim was ported to the browser. This is using like m script and these other technologies like web assembly. And so yeah, one of the challenges though, for something like, like this is, is, you know, the network stack, right? Because you can't really run a server, for example, in the browser and have other peop--or maybe you, maybe you can. Let me think about that.

[00:10:15] Actually, you kind of can, using a WebRTC and stuff like that. But it's definitely not a one-to-one mapping between, you know, these low level kind of Windows sockets, or Unix sockets and what you can do in the browser. And so, you know, that's kind of been an area where you haven't seen a lot of development, but here it's, they actually have Diablo II.

[00:10:37] I know, assuming they don't have the source code or anything like that. So this is just using the Diblo II binary. We are able to actually play in the browser and it's able to talk to a Diablo II Battle.net server. And you can actually play with other people co-op online, without even having to really do it, download anything, you just visit the website

[00:10:57] Which is pretty wild. I mean, I'll have to do a bit of research into how this actually works. My guess is maybe they hacked the, like, DOSBox emulator. And so, and so they, they somehow wrote a translation layer, where when you try to create a Windows socket, it uses WebRTC, which is just pretty amazing, or WebSockets or something like that.

[00:11:19] Pretty amazing. Check it out. It's clouddiablo.com. We'll have a link in the show notes, but I thought that was pretty wild achievement there.

[00:11:26] Patrick Wheeler: That is really awesome. And now I'm going to get depressing. I remember playing Diablo Iwhen it came out, and I was not a super young person when it did, and playing it really enjoying it, playing a lot. Do you know when Diablo II came out?

[00:11:38] Jason Gauci: You know, I've never, I played Diablo I, just the demo. I only played the demo though. So I've never been into the whole Diablo thing, but yeah, go ahead and tell us, when did it come out?

[00:11:48] Patrick Wheeler: 2000. So it's 21 years old, or it will be 21 years old in June.

[00:11:53] Jason Gauci: Oh man, that's nuts. Yeah, that's right. I remember right around, that would be senior year of high school for me.

[00:11:59] Patrick Wheeler: Oh, now you just, Oh no, no, now people are doing the math in their head, man. (laugh)

[00:12:03] Jason Gauci: Yeah. I'm going to hit the big four, oh, in I guess 10 months or something.

[00:12:07] Patrick Wheeler: Ohhh, okay.

[00:12:09] Jason Gauci: Yep. Diablo II had, if I remember correctly, Diablo II is the one that actually had like an overland map, right? 'Cause the one I played was just, you're in a town and there was a dungeon, and that was it. But then II added, like, a whole world, right?

[00:12:22] Patrick Wheeler: Yeah, like you walk around, and then you go into dungeons. Yes.

[00:12:25] Jason Gauci: Yeah.

[00:12:25] Patrick Wheeler: Yeah. The Diablo games are actually pretty fun. I enjoy them. I don't know. For me, there's like a whole layer of complexity, but I never really got into it, as like, you're number crunching, and min-maxing your character buildouts? So I never got competitive like that. I always just sort of like wandered around and like, you know, smashed a lot of stuff, and I always thought that was fun.

[00:12:45] But I never got super, super into it, but a lot of people really did. And for me, games that allow both kinds of players are super awesome. There's a lot of recent games that people get really into that I don't feel support casual or semi-casual play.

[00:12:58] Jason Gauci: Yeah. Yeah. Totally agree with that. You know, the, the games I've been getting into lately have been racing games, and I've been considering buying a steering wheel. The challenge is, if you buy a steering wheel, you also, they all come with the pedals, and I feel like you can't really use the pedal as if you're standing up and I have a standing desk.

[00:13:18] So it's like, it's like, (laugh) it's starting to spiral out of control. It's like, okay, first I need to buy a bucket seat and then I need to buy, you know..

[00:13:24] Patrick Wheeler: With the hydraulics to make it react to you.

[00:13:27] Jason Gauci: Yeah. (laugh) Yeah. So I'm not sure what to do, have a little bit of analysis paralysis. But I think maybe, I did see there's some steering wheels that have like, basically like a grip. So like the harder you grip, the faster the car goes. And so I might try and pick one of those up.

[00:13:42] Patrick Wheeler: Interesting. I think you need to like, come up with a custom, like DDR-style map for...

[00:13:47] Jason Gauci: Oh, that would be awesome. (laugh)

[00:13:49] Oh man. I've been playing this game Wreckfest. I just want to give a shout out to Wreckfest. They're not a sponsor or anything, but Bugbear is a company, and they made this game, Wreckfest.

[00:13:59] It's really interesting. So you, you have 24 racers, 20 are what you'd expect. They're just in cars, they're racing around the track, et cetera. The other four are in giant heavy school buses.

[00:14:12] And their job is to go around the track backwards and wreck like, the people in the top three positions. (laugh) So like, you'll be driving, it could be an oval or whatever, but like you'll be driving around the track, and all of a sudden, like a school bus will just, just crush you. So it's kind of like the blue turtle in Mario Kart.

[00:14:33] Patrick Wheeler: Are they, but are they computer controlled? Or like, it's like in, like some players are playing one and some players the other?

[00:14:38] Jason Gauci: Yeah. No, they're all real people. So it's kinda like if the blue shell is sentient, (laugh) it's just crush...

[00:14:44] Patrick Wheeler: Oh, oh all man.

[00:14:45] Jason Gauci: It's really, really fun. I highly recommend Wreckfest. I actually, you know, I never buy cosmetic stuff like just buy a new skin for your car or whatever. I never really done that, but I actually went and bought a bunch of cosmetic stuff in Wreckfest. I don't even use it. I just, I've put so many hours into that game that I was like, these guys deserve more than the 20 bucks or whatever it was.

[00:15:06] Patrick Wheeler: Interesting. I'll have to check that out.

[00:15:07] So your news article was a Diablo II in the browser, talking about browser games, but on a complete different level. This was something I came across that I thought was like, super cool. And one of those things, which we have said probably 500 times in the podcast, which is like, I wish this was around when I was learning to program. And that's Kaboom.

[00:15:28] And, the URL is replit.com/kaboom. And so I guess Replit is, they have a free tier, but it's also like a paid service, like IDE in the cloud, where you can run code and do development and stuff. I can't vouch for it. I haven't tried that.

[00:15:44] But this Kaboom thing is they were able to host a Java script game development library. If you do nothing else, search it and watch their opening video, which is like hand-drawn, MS Paint, pixel art, like, with just a hilarious, like, run up. And the audio is made by them. The drawing is made by them.

[00:16:04] And it's not meant to be the next blockbuster AAA title game engine. It's literally like, Oh, I want to drop a character here. And then it's like, you know, draw the sprites for your characters animation sequence, and you draw them in a little pixel editor. And then, you know, draw the wall tile, and you draw the wall tile and it manages the assets and your video game thing. And it's kind of not really like a, definitely not a no code way of building it, but just sort of this like right at your fingertips, like everything's sort of kept right there.

[00:16:34] And I imagine for complex games, it gets out of hand really fast. But for just making super simple, like a side scrolling engine and, doing ASCII descriptions of your text level, like, you know, equal signs for the walls and plus signs for where you want item pickups, and doing those kinds of things in a very simple environment, but something that really gets you into programming and allows you to make these.

[00:16:57] I think they're pretty, it looked pretty cool. Retro, nostalgic looking games. And I thought this was a really cool thing. Kaboom digest. I actually wonder if this was a way to try it easily in a, in the browser, which is how I was able to play around with it for a few minutes, but they may have a, I'm not a big JavaScript person, so I don't know how people pick up JavaScript libraries normally, but it looks like they also have, you don't need to go only on Replit. They have a way to do it. If you want to just host it yourself and try it. They have it available as well at kaboomjs.com.

[00:17:27] Jason Gauci: That's awesome. I'll have to check that out. And so, the idea is you, you draw the map in ASCII, but then you, for each, like ASCII character, you have a picture attached to it or something.

[00:17:38] Patrick Wheeler: Yeah, you just like has like the assets right there. And you say like, invent a new asset, and then it just gives you a little pixel editor and asks you to draw it.

[00:17:45] Jason Gauci: Oh, very cool. Yeah. I'll have to check this out. All right.

[00:17:48] My topic is on remote work. And so, so Patrick and I are both, well, everyone is working remote, but you know, at some point, offices are going to reopen and, I don't know, Patrick, if you've what your plan is, or if you know, or anything like that.

[00:18:05] But, but in my case, I'm permanently remote. So this is, this is the real deal forever and ever.

[00:18:10] Patrick Wheeler: Oh, ever and ever, that's a big commitment. (laugh)

[00:18:13] Jason Gauci: I mean, as far for who knows, but yeah, I mean, I'm basically a remote employee permanently. And so, and so, so you know, this whole like, "Oh, maybe remote wasn't a good idea" article is definitely scary to somebody who's really, there's no going back. But yeah, I think it's an, it's a really interesting debate. And I, you know, honestly, I don't have a lot of answers or insights really. I mean, I think that so far being a remote has been really great. I think we might have talked about this.

[00:18:40] I think we talked about this when we, we talked with Kevin. But, but yeah, we both have loved being remote, but then the question is, you know, when people come back into the office, what's the hybrid solution?

[00:18:51] That's really what it is, where it's, it's, maybe there's four people who are all sitting next to each other, and another four people who are spread out around the globe. How do you sort of, you know, keep the sort of social environment kind of like healthy and fair and all of that in, in that kind of world? And I think that's, that's what this article is kind of positing. And I don't know if there really any answers yet.

[00:19:12] Patrick Wheeler: Yeah, I think that's going to be a hard question for people. Like what does the future look? And then the debate we were even having at work the other day is, is this a kind of one and done thing? And then like, it just slowly over time returns back to normal, or like, is this going to keep creeping up?

[00:19:25] There will be at least, for some while, people's concern that it may come back, or that, you know, the next version, you know, the... in Silicon Valley, I guess the whole open office, densely packed people real estate at a super high premium is kind of very incompatible with the view that there might be reasons to not be super close to people.

[00:19:45] And so it's very interesting to see how we'll run a sort of real life experiment in the various ways of solving the problem over the next couple of years.

[00:19:53] Jason Gauci: Yeah, that's another really good point. I mean, a lot of companies in the Valley will have to double their office space, right. Because of the density.

[00:20:01] Do you think they're going to have laws around the density, or do you think it will be mostly like self-governance?

[00:20:06] Patrick Wheeler: I mean, laws is one of those things that's tough, right? Like at best case, I think laws are sort of slower, slower-moving, slower to catch up, which makes sense. I actually think that, you know, too fast lawmaking, you might end up in a problem.

[00:20:19] And so I think, what will happen is, the employees in some ways will sort of express what they're comfortable or not comfortable doing. And if, especially if there's a, like, I think Silicon Valley had gotten quite homogenous in the approach, and I think this will shake it up and allow for some experimentation to take place, which I think traditionally has been where you see a lot of innovation happen, right?

[00:20:41] And so I think we might be entering an era where you see some interesting innovation around this and a lot of people trying things, and the ones that will succeed will attract people to them, away from the ones that are on the other end of the spectrum.

[00:20:53] Jason Gauci: Yeah. That makes sense. I mean, one thing that, I don't know if I mentioned this on the show, but one thing I've been thinking a lot about is like, is it possible? And like, sort of safe from a privacy standpoint to like decouple your kind of work team and your social team, like, you know, look at WeWork for example, right?

[00:21:13] So WeWork as this company or this, this idea where, you know, they have a big office and you might go and rent one cubicle in this giant office, and the person next to you, and a person on the other side of you worked for totally different companies. You're just sharing this, like, you know, a physical space, right?

[00:21:31] And so, you know, if you wanted to go start, like, a ping pong club, you could do it with the people around you, even though, you know, the 12 of you work for 12 different companies. And so I wonder if that is going to, if that idea is really going to fly, where, you know, it's, it's like you kind of have a group of people and you have a whole relationship with them, but then you also have like your work team, which is spread out through, throughout the whole globe. And it's sort of like two different social networks, right?

[00:22:00] Patrick Wheeler: Not to get back into the avoiding drama at work you're talking about before. But I think it's been interesting. This thing you're saying a little bit reminds me of something I thought some about, which is, the different way different people treat their sort of a work team. And some people, the team becomes like an extension of their family, which makes sense. I mean, you spend, used to spend, you know, 40 hours a week minimum with those people basically.

[00:22:24] And in some ways that's more awake time than, you know, you often spend with other members of your family. And so for some people, they sort of re really bring those people in and treat them as family.

[00:22:34] Other people want to maintain a separation, right, between their, their sort of work teammates, and they can be sort of work friends with them, but there's a difference between a friend and a work friend, and they maintain that pretty solidly.

[00:22:45] And then of course people all along the spectrum. And then of course, people who have no interest in sort of the social aspects at work. And I've always thought it's interesting that how a person approaches that problem impacts how the work evolves. Right? So how the manager treats the team and their personal life separation probably colors how they view people on their teams, treatment of work stuff.

[00:23:09] That is, that was a really vague way of saying it, but like, if you come to work and your managers are very like super everyone's my friend, let's hang out all the time, and you want to maintain a stronger separation, that creates a bit of awkwardness. And so, I actually think this thing you're saying Jason, where like they get separated, for ill or good, I'm not sure, but at least it sort of evens out that some.

[00:23:29] If people realize I'm not going to be at work all the time, or we enter a hybrid, or a mostly remote work and people really understand that separation, and it's sort of somewhat forced in and you can still have fun with the people at work, but it's a little bit different. And I think that will even out the people who maybe felt trepidation or awkwardness with those relationships before.

[00:23:47] Jason Gauci: Yeah. That's a really good call-out. And so then, as a thought experiment, what happens to the other people? Like the people who, you know, always want to go golfing with the boss or something, but now the boss is, you know, a thousand miles away. Maybe, maybe people of that personality will, we'll just won't be remote. Right? They won't be a remote employees.

[00:24:07] Patrick Wheeler: Yeah. I don't know. Maybe they seek out a team or environment where for some reason or another, they sort of need everyone together or that's a culture thing or whatever.

[00:24:16] Jason Gauci: Yeah. Yeah. It's interesting. Yeah. That's pretty wild. Yeah. I think, I'm really curious to see what's going to happen.

[00:24:22] I wonder to what degree, like technology can help with something like this? Yeah. I mean, it's hard to know because we're not really in that situation yet. Like it's hard to kind of project what that's going to look like and what the social feelings are going to be. You know?

[00:24:37] Patrick Wheeler: I mean, I, for one welcome our, telepresence humanoid robot deskmates. (laugh)

[00:24:46] Jason Gauci: Oh yeah. All right. Cool. So on that note, Book of the Show.

[00:24:51] My book of the show is Debt: The First 5000 Years. I have to confess, I haven't read this yet. I just got it. But, you know, I'm always looking out for books on finance, finance, or just, the history of finance is just super interesting to me.

[00:25:05] And somebody at work, you know, sent me a ping, maybe a couple of weeks ago. And he said, Hey, you know, I read this book, you know, I think it's right up your alley. And so, I'm just catching up with, you know, I finished Antifragile and so I'm just kind of getting caught up with my current books and jumping into this new book. So, yeah, I have to admit I haven't read it yet, but it does seem really cool.

[00:25:27] I think that, if you think about it, like the whole thing around debt and credit and lending is, is really, really fascinating. Like it, you know, in my case, like I, I try not to have any debt if possible. I mean, there's things that, you know, there's large purchases that you have to pay over time, like you buy a house, or something like that. But, you know, on the credit card and some of these things, you know, I try not to have debt, but at the same time I don't preload anything either.

[00:25:54] So the credit card is super, super useful because I can make a payment on something that has zero balance using something that has zero balance and then, and then pay it later. And so, you know, I think, and then, you know, of course, like if, if for whatever reason I didn't pay it, well, now it's like there's debt. So it's like, you can't really have a credit card without debt. So it's kind of unavoidable. If you want to have that level of convenience.

[00:26:19] And you can kind of ask yourself, I mean, there's a lot of really fundamental questions about debt that I have. And I think this book will clear a lot of it up, like one of them is, and Patrick, tell me your take on this, but like, something is backed by the government. I still don't quite understand why they could charge interest. You know what I mean? Like, like how can you charge interest on a loan, if you're not actually taking any risk? Because, in effect the person who's paying the loan as like a, you know, a citizen of a country, that's also only backing the loan is actually taking the risk and giving you interest.

[00:26:52] So, that's just one thing, but there's, you know, debt is really fascinating to me. And I think this book is really going to explain a lot of stuff.

[00:26:59] Patrick Wheeler: Yeah. I think I'm going to opt out of getting into an in-depth fractional-reserve banking discussion and interest just now, like in here, this is going to, avoiding drama.

[00:27:08] Jason Gauci: I don't know. So, okay. A couple of things. So one thing is, is, yeah, I look at it just, just super objective. I don't have like a horse in the race per se. I just try to learn as much as possible. But the other thing is, is what is fractional reserve? Cause you mentioned that a while back and I always meant to ask you off the air. I never got a chance. So what is fractional-reserve banking? What does that mean?

[00:27:29] Patrick Wheeler: So, so you, you kind of were bringing it up by saying the, you were admitting the realization that the bank borrows money from the government at some level before lending out money. So the naive way of viewing a bank and I, I might mess it. I'm going to try.

[00:27:47] The naive way is that the bank has somebody come in and say, I'm going to give you a hundred dollars and then they say, cool, we're going to pay you a 0.001% interest on your a hundred dollars. Then they go find a mortgage customer who says, Oh, I want to use a hundred dollars to buy a house and you go, okay, cool. I'm going to loan out my hundred dollars to you that I got from this other person. And then you can use it to pay the person you're buying the house from.

[00:28:17] And then what I now have is someone who believes the hundred dollars is at the bank. But in actuality, it hasn't, it's been given to someone to buy a house and that person's making payments. And then the hope is that like when the, when the payments come in, that the person doesn't come and ask for their money back before it's there.

[00:28:36] So you can't loan out money that you don't have, unless you have a way of borrowing it. So the question is how much of the amount of money that you have loaned out your obligations, your liabilities for a bank, do you need to have in reserve? And that fraction that you need, is, is, is sort of governed by the government and saying like, you have to have this.

[00:28:59] Now, the difference is that you can also, sort of borrow money, but what happens with the whole fractional-reserve banking, if banks borrow money from each other or from the government, and keep a small amount in a reserve, and say, someone takes out a loan at Bank A, and then deposits it in Bank B, and starts earning interest, and then takes it out again and puts it somewhere else.

[00:29:21] Now, if you ask each of the banks, each of the banks will say like, Oh, I have a a hundred dollars deposited times three banks, but what if you've just gone in a circle, you actually only have a half a hundred dollars.

[00:29:32] Jason Gauci: Oh.

[00:29:33] Patrick Wheeler: And so fractional-reserve banking is pointing out this thing that you can sort of artificially create money by not requiring that banks fully back the deposits.

[00:29:44] Jason Gauci: Oh, I get it. Oh, it's interesting.

[00:29:46] Patrick Wheeler: And so the government can sort of, by controlling what percentage of liabilities are needed to being held and by the interest rate at which they're willing to loan you money and do these audits, they can sort of have a, I guess, not a direct, but an influence over sort of how much total money is circulating out in the environment.

[00:30:07] So, by lowering the interest rates from the government, they can encourage the banks to lend out money because they can lower their rates, which are like a delta on top of the, the government's rate. And so they can encourage people to take loans by making interest rates lower and lower, and thereby cause sort of inflation, right? By the money, there's more money, a parent money in the system. I probably didn't get that a hundred percent. Right. But that's the gist.

[00:30:34] Jason Gauci: Yeah. Yeah. No, totally makes sense. I mean basically if the government has a really high interest rate, then you could invest in that. I don't know what you would call that investing in, I don't know, the government or something. Yeah.

[00:30:45] Patrick Wheeler: You buy treasuries

[00:30:46] Jason Gauci: Yeah, yeah, yeah. Right. No, I know like the vehicle, but it's like, what are the treasuries actually doing? Are they just like building bridges or something?

[00:30:52] Patrick Wheeler: They're a bond backed by the government. So it's a government taking out a loan from you.

[00:30:56] Jason Gauci: Oh, I got it. So, so it's basically just going to whatever the government pays for. It could be anything.

[00:31:01] Patrick Wheeler: Yes.

[00:31:02] Jason Gauci: And so, and so, yeah. And so the higher the interest rates go, the more people who are going to do that. And that means there's less people who want to invest in other, like, private things. And so I think right now, the interest rates are very low. And so people are always looking for things to invest in, so real estate and other things.

[00:31:22] Patrick Wheeler: Yep. Okay. Yeah. That's going to get, if we keep going down this path, another few steps, it's going to get dramatic and political.

[00:31:28] Jason Gauci: Okay. All right. Let's not do that.

[00:31:30] Patrick Wheeler: The other thing I was going to bring up here, that's interesting. So I've, I've read the first sort of 50 pages of this book. Well, listen to the equivalent of about the first 50 pages of this book, because I have this book on Audible. But I haven't made it through, it's definitely not the most exciting read at least in the first few pages, but I'm also intrigued by this concept. And it also plays into the thing that we've been a common theme here on the, on the show, which is the cryptocurrency and blockchain. And this concept of DeFi this distributed finance, and how would you allow on the blockchain, people to borrow money, by depositing one asset and taking money out of, you know, some sort of contract and going and using that money and then paying back that debt over time. And how would you handle that if it needed to be done all via algorithm and not by human intervention or judgment?

[00:32:19] Jason Gauci: Wow, that's actually in the book?

[00:32:20] Patrick Wheeler: No, no, no, I don't think so. I'm just saying this conversation we're having about fractional-reserve banking, inflationary versus deflationary politics, and the common theme of cryptocurrency leads to a very interesting topic, if anyone wants to go sort of look in that and hasn't yet about this distributed finance. I don't think it's in the book.

[00:32:36] Jason Gauci: I haven't seen anything about crypto derivatives. I mean, I'm sure it exists, but I haven't, it's definitely not a popular thing.

[00:32:43] Patrick Wheeler: Oh, the book was written in 2011, so yeah. There's zero chance it's in there.

[00:32:47] Jason Gauci: Oh yeah. Oh, there you go. I think crypto derivatives would be a pretty interesting thing, but, but then the thing is like, how do you do that?

[00:32:54] Because derivatives have to trade faster, presumably, have to trade at higher cadence than the original thing and, and crypto is, is so slow. I mean, you have to somehow make the algorithm, the whole process would be much faster.

[00:33:08] Patrick Wheeler: My book of this show is not well-suited to, audio edition in the format I'm going to recommend it, but that is a Harry Potter and the Sorcerer's Stone, the Illustrated Edition.

[00:33:18] So we've talked about before, both Jason and I have children, and my children are now old enough to sort of start introducing them to Harry Potter, and they're getting interested in reading. And so I figured to, to read to them, I would read Harry Potter and the Sorcerer's stone. And then I decided to go in and pick up the Illustrated Edition just to kind of keep it more, engaging for them, unless at least until we saw how it went.

[00:33:43] And Oh man, I read Harry Potter, I don't even know how long ago. I'm not... long ago. I went back like when they were first coming out.

[00:33:51] Jason Gauci: It also, it came out around the time Diablo came out.

[00:33:54] Patrick Wheeler: Oh, did it?

[00:33:55] Jason Gauci: I think so. Yeah. Correct me if I'm wrong, I'll look it up.

[00:33:58] Patrick Wheeler: But going back through it again, and reading it and then like, also seeing the pictures, they're just so well done in this book. These books aren't cheap. Like I've gotten used to like really cheap books. These books are just very well done though. The drawings, even the pages that don't have sort of full color illustrations have like texture to the page, and it's not just a black and white.

[00:34:16] Small nit is like, there are some places where the text is a little hard to read against the background. But, just like thematic and sort of, you know, nice to look at, and just a really nice book to read, and sort of go page by page through. I've really enjoyed that, so...

[00:34:32] Jason Gauci: Harry Potter and the Sorcerer's Stone came out in 1997.

[00:34:37] Patrick Wheeler: We're going to keep going. (laugh) So if you've not, if you're interested in Harry Potter or if you have children or you've never read it before, or if you just really like pictures, you know, I don't think it's probably everyone who's into this, probably seen these before, but anyway, my recommendation is Harry Potter and the Sorcerer's Stone.

[00:34:54] Jason Gauci: So it's not a small book. Right? So how does that work? Is there a picture every few pages or is there one every page or what's the...

[00:35:01] Patrick Wheeler: So the, I mean, the book is both large in sort of height and width, and then also it's sort of normally deep, so it's a little bigger than a normal book that you would not want to carry this book to the beach and read it on the beach or whatever. Like it's a bigger book. And then, you know, also-- And there's, you know, so every page has like some sort of like thematic texture drawing to it if I recall, but then yeah, sort of every other page or every third page pair will have like some picture related to the things sort of like off to the side or in the corner.

[00:35:30] Jason Gauci: So is it abridged or is it like actually the whole book?

[00:35:33] Patrick Wheeler: No, it's the full thing.

[00:35:35] Jason Gauci: Wow. That's cool. Yeah. I find out about so many good products on this show. (laugh)

[00:35:41] Patrick Wheeler: This is like, what is it, Oprah? Who does the Christmas best things or things you have to buy--

[00:35:46] Jason Gauci: Yeah, that's right. Yeah. Very cool. I'll definitely be picking that up.

[00:35:49] Patrick Wheeler: So, so I alluded to it, and, and, I actually do have Harry Potter and the Sorcerer's Stone on Audible, but it's obviously not illustrated, but it is well narrated and it's a very pleasant way to consume the book.

[00:36:02] But if you've never tried Audible before and you can check it out and help sponsor the show by going to audibletrial.com/ProgrammingThrowdown, and there they'll do a free one month trial of Audible, which, you can pick sort of any book that's in Audible, download it and you get to keep that book.

[00:36:18] And then you can cancel the trial if you decide you don't want to keep it, or keep going and get a book a month. I've done that for awhile, you also get access to their sales and I've built up, quite a collection. But, you know, honestly, I really enjoyed, I don't have a bookshelf at home with dozens and dozens and dozens of physical books. It's just not a thing I do anymore, but I do enjoy actually scrolling through my Audible list of books and picking out my recommendations for the show.

[00:36:43] Jason Gauci: Yeah, very cool. And for folks who either already have an Audible account, or aren't interested in that, they can support us on Patreon. So Patreon and Audible are how we can keep this show going and how we were able to get more content.

[00:36:57] I mean, this episode exists because of your support. And so we really appreciate that. You can reach us at patreon.com/ProgrammingThrowdown.

[00:37:05] Patrick Wheeler: It's time for Tools of this Show.

[00:37:09] Jason Gauci: My Tool of the Show is Vagrant! Have you ever used Vagrant, Patrick, or are you new to Vagrant?

[00:37:15] Patrick Wheeler: I feel like I know the word, but I'm not thinking of what it is right now.

[00:37:20] Jason Gauci: Okay. So Vagrant is, it's similar to Docker. We talked about Docker on an earlier episode, but it is for virtual machines. So Vagrant is a way to spin up a virtual machine, and to initialize it with a set of, sort of, you know, parameters and, and, and a set of scripts.

[00:37:41] So for example, I use Vagrant a lot when I'm testing new versions of Eternal Terminal. So before I release a new version, which is kind of a big process, you know, it goes to all the Debian and Fedora, like official, you know, like the package systems, and it runs through a million different tests. People like download it. I want to make sure that at least like all the tests run and build and everything.

[00:38:05] And so I have a set of Vagrant scripts. And so the way this works is similar to Docker, you know, you write a Vagrant file, and in that file, you say what the virtual machine should be like. It, should it be Ubuntu, should it be Windows, should it be, you know, Fedora or openSUSE or whichever one, and then you specify the things, like how many CPU's should the virtual machine have, et cetera, and you can specify scripts.

[00:38:34] So in my case, the script goes to GitHub, grabs the latest Eternal Terminal release and, builds it, and it runs all the tests, and then, and then kind of exits, right?

[00:38:47] And so all of that, you know is nice because, for example, there was a, a GitHub issue the other day where someone said, Oh, the open... and I don't know how you pronounce this.

[00:38:56] It's open S U S E. Open... susie? But that, that variant of Linux, you know, wasn't compiling and, I just pointed them to, to Vagrant. I said, Hey, you know, install Vagrant, run Vagrant up in this directory and you'll see it totally builds the works. And it turns out that the person who actually maintains the openSUSE package, who, you know, isn't, isn't me, that person, there was some error there. I don't actually know the details, but I was able to just, you know, get anybody to, to just go on there and, and run and build, which is super convenient.

[00:39:29] Now you might say to yourself, well, if you have Docker, why do you need this? Right. And the answer is, you know, there is that layer in between Docker and the virtual machine, right? There is the whole, the Docker, like Docker daemon, right? And so Docker tries to, you know, be really good about, you know, giving you a lot of freedom and flexibility, but when you're doing things like building packages or especially you're doing things which involve low-level networking, you know, that can give you results that aren't really natural, and sometimes you really need like a bare bones virtual machine.

[00:40:04] And so Vagrant is kind of like the Docker for that, for that kind of stuff. So, if you need that, check it out, it's super, super useful. Especially if you're deploying software on a bunch of different OSS, you know, I literally have just one script that I run and I can test every OS. And when the script finishes, I know like every OS works. So it was just a one-liner and so I'm a big fan of Vagrant.

[00:40:28] Patrick Wheeler: Nice. What is the difference between something like Vagrant and VirtualBox?

[00:40:33] Jason Gauci: Oh yeah. So under the hood Vagrant uses VirtualBox. I think Vagrant is just like a scripting library for VirtualBox. That's a good way of looking at it.

[00:40:42] Patrick Wheeler: I see. I see. Okay.

[00:40:43] Jason Gauci: The other thing it does is, it maps like a folder on your computer to a virtual machine. So if I do,like Vagrant up in a certain folder or with a certain Vagrant file, it, it has a UID for that file. And if the machine already exists in VirtualBox, then it won't have to like totally destroy it and bring it back up and stuff like that.

[00:41:04] Patrick Wheeler: Nice. My Tool of the Show, I actually had one, and then I switched it to a collection, because indecisiveness. I was playing a new game by Zach Gage Games, and that was Good Sudoku. So I, I played Sudoku for awhile. I go off and on in books, but I never really got into it just didn't feel the same.

[00:41:22] Like I couldn't use my pencil to kind of make notes on iPhone or you know, on an Android phone. I use an iPhone, but I I'm sure it works the same. And so, you know, I kind of never really did it, got into it on, on mobile, but then I tried this Good Sudoku, and I didn't realize it was by the Zach Gage Games, but I tried it, and they just liked the kind of UI they built up around playing Sudoku.

[00:41:44] It's not exactly the same as how I would do it on pencil, on paper. It plays a little faster. It does actually what I want. And I just really thought it was very well done. And then I realized, like I was searching this, you know, Zach Gage Games, this is a maker of, of Good Sudoku. And then I'm like, Oh, I actually like a lot of these games.

[00:42:01] So they're the people that made Ridiculous Fishing, Really Bad Chess. So Ridiculous Fishing is like, you're a dude on a fishing boat. And then you use like the motion sensor in your phone to drop a line down into the depths of the ocean, catch a fish and then sort of reel it back in. It's ridiculous.

[00:42:18] Jason Gauci: Did you reach the end of that game?

[00:42:19] Patrick Wheeler: No. Uh-uh.

[00:42:20] Jason Gauci: Oh, okay.

[00:42:21] Patrick Wheeler: Do I need to?

[00:42:22] Jason Gauci: I'll spoil the ending after you explain it. (laugh)

[00:42:25] Patrick Wheeler: No, don't spoil it! No, you can tell me offline.

[00:42:28] Jason Gauci: Okay. All right. I won't spoil it, I won't spoil it.

[00:42:30] Patrick Wheeler: No, I need like a week, give me a week, I'll go do it. Now I know there's an ending.

[00:42:33] Jason Gauci: It's actually pretty good.

[00:42:35] Patrick Wheeler: Oh, okay. So Really Bad Chess is, you know, I know Jason is like, a master chess person, so we're not going to, (laugh) we're going to ignore him for a second. But, I'm really bad at chess actually. So in this game, they don't even try to make an attempt that decides white and black or even, it is effectively, randomly placed chess pieces on your side of the board. So you might have like five Queens and the other person has all pawns. Or something you'd only get one King or something, you know, and then you try to play.

[00:43:03] So the expectation is just to like, be a little more goofy and a little free and make it not have to be, this super serious, chess game.

[00:43:12] Anyways. So if you've never checked out any of these games ,Good Sudok, Really Bad Chess, Ridiculous Fishing, some are available on iOS, some on the play store. Go check them out. They're actually this, I didn't know anything. I need to go learn more about this company, but it turns out right before the show, just doing research. It turns out I'm actually really into these games and I'm going to follow them and watch for new ones that come out.

[00:43:31] Jason Gauci: Oh, very cool. Yeah the Really Bad Chess sounds awesome. Do you play online with people or is it against the computer?

[00:43:37] Patrick Wheeler: You know, I, I played it once, and I don't do online playing, so I actually don't know if you, I'm sure, there's probably like this based on it. There's a way to do it. Multiplayer. Is just for me. I never, it always feels embarrassing even though it's... (laugh)

[00:43:51] Like, I don't want to lose to real people. I don't care about losing to the computer, but... (laugh)

[00:43:56] Jason Gauci: You know, when we, when we first moved, my family first moved to, to the West coast, I actually set up a meetup group called, Sports for People who are Really Bad at Sports. And, it was great because, you know, you kind of self-select for people who aren't going to take it real seriously.

[00:44:14] And it actually, I was worried that like, somebody would see that title and be really good at ping pong and then just kind of embarrass us and like, I have to deal with it. But no, actually like everyone who showed up genuinely was really bad at sports and we all had a really fun time.

[00:44:28] Patrick Wheeler: Oh, that's cool. It does not look like Really Bad Chess has multiplayer. It looks like it's only single player.

[00:44:33] Jason Gauci: Oh, okay. That, that, it kind of makes sense. 'Cause I think that could be more frustrating.

[00:44:37] Patrick Wheeler: I think it's supposed to be more like, it's kinda like puzzley, right? Like they sort of know like here's the best you could do with this crappy set of pieces. And if you play multiplayer and one person got like, decidedly, a good advantage against you and they win. So what?

[00:44:52] Jason Gauci: Yeah, exactly. Like, like, like teasing apart, the computer's kind of strategy is part of the fun, and part of it's kind of gone if you go online.

[00:45:03] AD: Hey everybody, we have new sponsor, and that is ConfigCat. And I'm going to tell you a little bit about, what ConfigCat is. It is a feature flag service. You can easily use flags in your code with ConfigCat libraries for Python, nine other platforms, toggle your feature flags visually on the visual dashboard.

[00:45:22] Hide or expose features in your application without redeploying your code. Set targeting rules to allow you to control who has access to those new features. ConfigCat allows you to get the features out faster, test in production, and do easy rollbacks. With ConfigCat, simple API and clear documentation, you'll have initial proof of concept up and running in just minutes.

[00:45:43] Train new team members and minutes easily, so you don't have to pay extra for growing teams. With a simple UI, the whole team can use it effectively. Whether you're an individual or a team, you can try it out with the Forever Free plan.

[00:45:57] Release your features faster and with less risk with ConfigCat, check them out today at configcat.com.

[00:46:03] Jason Gauci: Cool. Yeah. For people that don't know what feature flags are, it's, you imagine you have something out in production and you want to change some kind of behavior. So you might say, you know, now use this other database, but then you do that and then it's broken and now you've broken it for everybody. And that's, that's kind of a nightmare.

[00:46:20] So, so what you want to do instead is you want to try something out on like a few people and then slowly kind of add more and more and more people. And one way to do that is to have a feature flag, have a flag says if you know, this is part of my test group of people, then switch to the new database.

[00:46:38] Otherwise use the old database. And, and slowly like that, if becomes true for more and more people. And so ConfigCat is a service that, that kind of handles a lot of that for you. So they can like handle deciding, like who gets the feature and who doesn't. And then you can go in their UI and change all of that and slowly, slowly get it to a hundred percent and they take a lot of that burden off you. So check them out. They're great.

[00:47:03] All right. So we can jump into trees.

[00:47:08] Patrick Wheeler: Why are trees important?

[00:47:09] Jason Gauci: Why are trees afforded? So, so, just a quick story, you know, a lot of search indexes and e-commerce sites, so if you go to Amazon or you go to Google or you go to any of these websites, you know, they need to serve content to you really quickly.

[00:47:27] And the way that you can do that, especially in a place where you're adding a lot of content, very dynamic, you, you're going to be using hash tables, which we'll talk about another time, and trees, and, and especially trees.

[00:47:42] And so for this, you could say money grows on trees. If you work for Amazon, money literally grows on the trees. And so that's, that's why it's so important. If you're going to be doing queries, insertions, you're going to be doing partitioning of data, you are going to use trees a lot, and they are extremely important. They're going to come up all the time.

[00:48:03] Patrick Wheeler: I think it's also one of the like, first things people learn in computer science because I feel, and you get this like, if you look on the internet, you get the, Y if I interview at X tech company, do they ask me about binary trees or about linklists or,...and, you know, I, I somewhat, I hear, and there's there. I don't want to get into the drama or the politics (laugh) or whatever around all of that. But what I'll say is that, you know, being able to think through trees and their trade-offs and, so it's just like, it's part of, you know, kind of like the problem solving, even if like Jason and I were talking before.

[00:48:38] So some of these trees we're gonna talk about, I definitely use and use them all the time, but the sort of basic vanilla binary tree that, that most people are introduced to first, like actually have trouble coming up with exactly how I would use that one. and it's not clear if it has a ton of use. But as a learning tool or reasoning tool or thinking tool, or like a, a minimum backstop, like I got to at least do better than this, it actually serves a really good purpose.

[00:49:03] Jason Gauci: Yeah. Yeah, totally. I think that, I mean, the thing that trees teach people at a fundamental level is the idea of, sort of divide and conquer and also like Agglometric thinking. So we'll jump into like how trees are built and hopefully we can use that to kind of motivate why they're so important to know about.

[00:49:22] So, you know, imagine if you have, you know, some set of numbers and you need to put this set of numbers into a tree, and we'll get into why you'd want to do that late,. But imagine, you know, your task is sort of doing this, you have this binary tree and you want to, you know, you want to fill it full of these numbers and you want the tree to be pretty balanced and stuff like that.

[00:49:43] So there's two kinds of ways to do this. One way is, sort of divide and conquer. So you can imagine saying, well, what I'll do is I'll, I'll start with all my numbers. So I kind of in a way have like a single node that just has my entire set of numbers in it. And then what I'll do is I'll just split the set into two halves.

[00:50:06] One half is the, the bottom 50% of numbers, right? The bottom half of the numbers, if I was to order them, like maybe you'll sort them and then cut that sorted list in half. And then say, you know, I'll send that half down the left side of the tree, and I'll send, the bigger half down the right side of the tree, and maybe I'll take the node that's right in the, on the median and make that my node.

[00:50:28] So, you know, imagine like you have 20 as the root of the tree and everything to the right of 20 is bigger, everything left of 20 smaller. And so now you can repeat that process again on the left and right side, right. You have a less than half the size of your original set, but that process stays the same.

[00:50:47] And if you were to just go to that, that left branch, that has those, that half of numbers, and just look at it in isolation, you actually have the same problem as you did in the very beginning, just with fewer numbers. And so trees are a really good way to explain recursion and to, you know, deal with all of that phenomena. And to cover a lot of other phenomenon in computer science. Right?

[00:51:13] So, so trees are kind of, you could even think of like the call graph when you're doing recursion and we're doing computation as, as sort of this, this tree, like the history of all the functions you've called. So, so yeah, trees are kind of ubiquitous. And so, you know, it kind of like introduces you to a lot of other areas of computer science.

[00:51:34] Now, another way to build trees is what we call Agglometric or bottom up. Well, to do the same thing, like an Agglometric way, you might say, I'm gonna take all my numbers, I'm going to sort them. And then I'm going to group them into, you know, 16 different groups.

[00:51:56] And then for each of those groups, I'm going to, you know, pick a number out and put it and call it like the leaf node of that group. And then I'm going to, you know, do that and then kind of go bottom up and then start kind of merging some of these mini trees together.

[00:52:14] So now it's like, I have a bunch of these smaller trees, I'm going to kind of merge them, merge them, merge them. And when I'm done, I have one big tree. And that's kind of the Agglometric way of assembling these trees.

[00:52:26] And so, and so, you know, that is also, you know, if you look at, for example, merge sort or something like that, you actually see kind of both of these things, right? So in merge sort, you start by kind of splitting a list into halves and then halving it, halving it, halving it, just these successive halfing algorithm. And then at some point you reach a point where it's just all just lists of size one, and then you start kind of merging, merging, merging. And so, you know, merge sort actually has both, you know, a divide and conquer approach and then an Agglometric approach to kind of bring everything back together. But when it comes back together, it comes back sorted.

[00:53:03] Patrick Wheeler: Oh. I didn't know that had to name.

[00:53:06] Jason Gauci: Yeah. Yeah. So, so it's, so then, then you have this question of like, how do you go about doing that divide, right? Like if it's, if it's small, you know, like for example, you know, you have 100 items and you're just putting it into some binary tree. Well, then you can, you can kind of what we talked about, sort it and then split it, and you'll have this like perfectly balanced tree that look really nice.

[00:53:28] But in practice you're dealing, with like massive, massive datasets. And so you can't, you can't really, you can't really do that. It doesn't really make sense. Or you might even have things that are multi kind of modal or multi-objective. So there might be different ways to split data. You know, maybe you have a list of people, and those people have, you know, ages, they have genders, they have other characteristics, and you want to have some binary tree that says, you know, that ultimately like results in different equally sized buckets of people.

[00:54:07] So your binary tree might say something like, well, let's first look at everyone who's over 18 is on one side and everyone who's under 18 is on the other side. And it's everyone who has been to my website in the past a day is on one side. And so in this kind of decision tree,at the end of all of these decisions, at the end of all, asking all of these questions, you now have this, you know, end state, which hopefully doesn't have too many people in it.

[00:54:35] And so, you know, you know, whether you're doing a decision tree like that, or you're doing just a, you know, a sorted tree, but have a really large dataset, you can't try every possible way to, to, to construct that tree. It's just too expensive. It's I think it's like NP-hard. Like coming up with the best possible decision tree.

[00:54:57] And so that's where you end up with trying to do some of these approximations. So you might try, you know, at every node in the tree, you might try 50 or a hundred different ways of splitting it. Now there might be thousands, but you're just going to try 50. And because you're trying 50, you might not, you know, get the best way of splitting, but hopefully the best one out of 50 is decent.

[00:55:22] And then when you go to all these children that you've created from the split, you're going to do this again. And you're going to pick 50 at random, a different 50 ways of splitting. And if there was a really good way of splitting that you missed, hopefully like you catch it, you know, at the next level.

[00:55:40] And so this is how a lot of these decision trees or binary trees over really large data sets are kind of assembled. There have been a lot of other like search-based approaches, but, It's actually really hard to beat the, just a greedy way of doing it.

[00:55:57] Patrick Wheeler: So, so to back it off of, back to the, kind of like the basic stuff, I think Jason was already jumping ahead that we, or at least me. I tend to think of trees as storing, like strictly orderable things in the data, like numbers, or strings. And, one of the other things to point out is that you may not be exposed to all of them all up front. So if you are experiencing them over time, having these things that Jason's talking about and figure out how you split, how do you insert new data or remove data or modify data plays a part too, and what tree and algorithm you might select.

[00:56:39] The other thing that I, that has come into play for me is that, I often think about first about trees as being sort of, no individual allocated nodes with pointers between them. (cough) I work in C++ (laugh) That's how I think, but they don't have to be actually. In fact, in some cases, in many cases, it may be better served to have an array of all of your data and then order the stuff in the array where like the zero item in the array is your root node.

[00:57:08] And then the, you know, first and second, are the children nodes. And then you can do sort of what level are you on and where in the level are you, and then you can do the visitation of the nodes and the search by simply going to the right place in the array. and that has efficiencies for keeping your data, you know, more close to each other, more local, and that's more cash efficient, and we're going to get into some other things where that plays a role as well.

[00:57:33] But I think it starts off when you're first introduced trees is, in my experience, like this very rigid. They're always binary trees. In fact, they're normally always binary search trees, and you always divide them up in a, in a certain way, but actually the sort of body of all kinds of trees that are using computer sciences is quite big and they often share interesting similarities, but also very interesting differences.

[00:57:56] Jason Gauci: Yeah. Yeah, totally makes sense. Yeah. A lot of people have invented, different trees for different specific use cases and, and a lot of it comes down to, you know, being able to split the data in a way that more often than not splits evenly. Right. Because what you don't want is, and you'll hear this like trees that are balanced or unbalanced. Right?

[00:58:18] So imagine if, imagine if you have a binary search tree over, over numbers, but it's completely unbalanced. So the root node has, let's say, let's say you have the numbers 1 to 100, the root node has a one. It has just one child to the right. That's a two. And you just do this all the way to a hundred. Now you actually have a linked list, right. You used the tree idea, but you ended up with a linked list and, you have all the performance problems of a list, right? If you were expecting something to be really, really fast, you're, you're not going to get that ex, you're not going to meet that expectation. Right?

[00:58:57] And so you want these trees to be balanced, but you also, as we talked about before, like you can't spend a lot of time building it because you're dealing with such large volume, right? So you can't look at all of the items, do many, many passes. And so a lot of these structures that we'll get into have really nice kind of like a really nice propensity to just naturally break data down into ways that are even, you know, for a specific type of problem.

[00:59:26] Patrick Wheeler: I mean, yeah. I think the algorithms for keeping them balanced are probably slightly difficult to communicate over audio.

[00:59:33] Jason Gauci: Yup.

[00:59:34] Patrick Wheeler: But what are some of those, what are some of those ? If people want to look them up?

[00:59:39] Jason Gauci: Yeah, it's really good point. So, so in addition to like choosing the right tree, and people are inventing new types of trees all the time, you know, no matter what you do, especially if data is coming in and going out, you know, the trees will become unbalanced, either when you're building it, or when you're modifying it.

[00:59:56] And so there is, you know, there are special kind of trees called AVL trees and red–black trees. And, and for things like b-trees, there are ways to rebalance them. But as Patrick said, I mean, you know, definitely, take a look at, if you search for any of these trees on Wikipedia or other places, you'll see really nice kind of visuals of how they're rebalanced.

[01:00:19] But, I remember from, from, you know, undergrad, rebalancing trees is one of the hardest things that I have to implement. And I just remember having so many issues because you have to kind of project yourself into different parts of the tree and like, think, okay, at this point of the tree, you know, I, I am like, like I'm at this node in the tree, but because I'm in the middle of this rebalancing, I know this, this and this.

[01:00:44] And so I have to do that. And, so that, that's what gets really, really difficult. So yeah, I think in general, you know, if you're going to use trees, try to find a library on the web, you know, definitely take the time to understand how they work, but if you're going to put something into production, there's, there should be a really good implementation of a variety of different trees that are, that's publicly available.

[01:01:10] Looking at binary trees specifically. So, you know, a binary tree is one where you only have two children. And so you might see yourself, well, like why would I, why would I, you know, have that restriction, right? Like, what's, what's, why would I limit myself, right? But there is one thing that binary trees can do really, really well. And that is like upper or lower bound search.

[01:01:35] So for example, imagine if you have a set of numbers and, and you're asking the question, you know, what is the biggest number in my set, you know, less than 30, right? That question requires you to, to do kind of an in order search.

[01:01:54] So you have to kind of look for 30, if you find 30. Well, I guess I said less then, so, so yeah, even if you find 30, you still have to kind of go backwards. And find the biggest number less than 30. So you have to kind of March in sorted order through that structure, right? And a binary tree is really nice because, since there's only two children, you know, that the child to the left is smaller, and assuming there's no duplicates in the tree, the child to the left is smaller and the child to the right is bigger.

[01:02:26] And that's always true. And, and you can also do this trick where if you take any point in the tree, if you take the child to the left and then keep going to the right as many times as you can, you're going to get the number that is smaller than the one you're currently at, but bigger than, than, all the other ones. And so that's, that's a unique feature to binary trees. And I think that is one of the biggest reasons.

[01:02:52] Another reason why people use binary trees is in machine learning. We talked about there's, in machine learning, you're typically not using a tree to store a lot of numbers or something like that, you know, you're using a tree to the structure of the tree to store decisions.

[01:03:10] And so at the end of you got the, the, the leaf or the end of a binary tree, if you've searched through it, you have kind of a list of constraints and you can use that as a, as a way to learn things. Right?

[01:03:24] So in that case, it's actually pretty difficult to split it multiple ways, depending on what kind of decision you're making. So it's, it's decisions like, you know, this number should be greater than X or, you know, this binary number should be set to true. Like these are all kind of binary kind of decisions like thresholds and binary operators. There might be times where you have some kind of categorical thing. So, you know, day of the week, it could be seven choices and you should have seven children.

[01:03:59] But, but even in those cases, it's, it's kind of hard to calculate whether that is a good decision to put in your tree or not. Versus if you have a binary. Yes. No decision. It's pretty easy to calculate. Yes. I want to take that decision and put it here in the tree. And so for that reason, a lot of machine learning will use, will use binary trees, when they're making these decision trees.

[01:04:25] You'll also hear in machine learning the term random forest. At the time, I thought random forest was this really complicated thing because I had heard, you know, where it was used. And so I thought, Oh, like one of these days I really want to learn random forest. Random forest is very simple. All it is is if you have a big data set and you're planning on building a decision tree, instead, what you can do is you can split that data set, you know, end different ways and build end different decision trees.

[01:04:56] And, you know, because of that randomness, I talked earlier about where, where you're randomly trying different splits, even if the, the, the, the distributions of the data or the type of the data is the same in each of those groups, you're still gonna end up with different decision trees. and then once you have all of these decision trees, when you want to make a decision in the future, you can actually ask all of them, and then you can either do some kind of voting, or you can take the average, or what have you.

[01:05:28] Patrick Wheeler: So Jason already spoiled our next topic, but if binary trees have, two children at each node, if you generalize that and instead allow sort of more children, there are a variety of things you can come up with, but one of them is a b-tree. And so b-trees say that each node can, and there's some variance here, but basically each node can contain multiple values.

[01:05:55] And then the chil-- however many values it has, you have that many children plus one. So let's say you had two values stored there instead of just one, then things before the lowest value, you keep them sorted, and then the thing below the lowest value you would have reference to the next child there. Between the two values, you would have a child, and to the right, the bigger, the biggest larger than the tube, the bigger you would have a child to your right.

[01:06:26] So in that case, you had two values in the node and three children, and you could see this expanding to, various sizes four or five, six, seven, and there's a lot of varieties and some techniques for how you keep them balanced. But the interesting thing about here is when you visit a node, rather than simply making a single decision, do I use this value? Do I go to left or right. You sort of can consult multiple values. And then also you make, by doing that, you make your tree shallower. So you don't have as, as many levels of children as you would, if you used a binary tree, because you're putting more, more data, in the note.

[01:07:04] Now, the other thing that I already hinted at as well, where this starts to matter, and this is one of those things where, when I'm doing interviews with people and we do some sort of, you know, questions, we're working through a problem and then I'll often ask them, you know, Oh, what is, what is sort of the run time? And they start scratching their head, and this is different for everyone, but always express to them, look, I'm actually not that interested in sort of the academic, asymptotic runtime, because it turns out like, in my life, most of the time you're dominated by other factors. So I'm looking for you to just express to me like, which parts of this algorithm, about how many times would this take, where are your bottlenecks?

[01:07:43] And so one of the things that b-trees really excel at is, if you imagine, which was true, maybe a lot more true five, 10 years ago than is true today. But if you go back 10 years, RAM was really small, like CPU caches weren't really like they are today. And things were stored on sectors on hard drives.

[01:08:04] And if you were going to go access something on the hard drive, the hard drive is going to spin up, move the little arm out to the right spot on the moving piece of metal with magnetised bits on it, and read in a whole bunch of data in a sector, and bring that into memory. And that was an extremely slow thing.

[01:08:21] And so if you were going to do an on disc search for data, you wanted to bring in, sort of as much in one go as you can. And if you imagine a binary tree where at each block, you have one and then the next block is, who knows where, each time you go to the next node, you are spending a lot of time waiting to get the next node into memory or getting into the CPU.

[01:08:42] And these b-trees became very valuable by instead saying we're going to store a whole bunch of data in the sector. Then we're going to analyze all that data, increase our chances at any given node of finding ours or at least, cutting down the search set dramatically. So the number of different nodes we have to visit is as small as possible.

[01:09:00] So for things like file system and file system metadata, for things like databases and indexes and databases, like, these b-trees get used heavily because, you can tune the number of children and you can do sort of more work per node visitation. And if node visitation is a dominating factor, then you would want to choose a b-tree. And then there's techniques for making sure that you keep all the data at a certain spot that you know how to keep it ordered and organized and well balanced.

[01:09:30] And so there's a whole body of work around b-trees, but it's enormously valuable in this sort of broadening the scope out from just, you know, one value and two children to allowing a more general form and realizing that that may play better with an actual, computer architecture.

[01:09:49] Jason Gauci: Yeah. Really well said. Yeah, that really covers it. And so, yeah, as Patrick said to me, pretty much any database that you look at is going to have a b-tree implementation in it. I mean, all of them, they all use b-trees in some way, shape or form.

[01:10:04] So now we'll move on to spatial trees. And as we, you know, motivated earlier, you know, spatial trees often aren't functionally, you know, that different or, or, you know, in terms of their idea, but they're just taking advantage of some domain knowledge, in this case, the fact that, that, that, it's operating over some, you know, some, some space or some field, right?

[01:10:28] And so the simplest one of these that I know of is a k-d tree. I don't actually know where the name k-d came from, but, but effectively it's a binary tree where every split is done on a single axis. And so if you imagine, like, so like picture in your mind, you know, a graph like just with an X and a Y, right, graphing some function. If you just have a line, right. You can describe a line just by looking at one of the two letters.

[01:11:01] So if you look at just a horizontal or a vertical line, you can do that just by looking at one of the two variables. Right? So if I have a line like Y equals X or a parabola, like Y equals X squared, I need to be thinking about Y and X at the same time., bacause they kind of relate to each other. So Y equals X squared, you know, as, as X is increasing, Y is really increasing. And so you have this like parabola, right? This line that like just shoots upwards. Right?

[01:11:28] But if I have a, just a vertical line, that's just like X equals two and I want all the Y, right? That's a vertical line. Or if I have a horizontal line that would be, you know, like Y equals four. And so, and I just want all the exes that are all points on that line. So vertical and horizontal lines are kind of the easiest to express. Right? And so k-d tree uses this to, you know, to, to have a very simple division of, of, of the space.

[01:11:58]So what a k-d tree will do when you're building one is, you'll look over all the points and let's just keep it at two dimensions, just to keep it simple. So you look over at all these points and then you'll calculate the spread. In other words, you calculate the difference between the smallest point and the biggest point on that dimension.

[01:12:18] So if you were imagining like, you know, a bunch of points, but, but they're all kind of around the same height, but there are some that are really far to the left. Some that are really far to the right. You have this really large, horizontal spread, but not a very large vertical spread. And so whichever dimension has the largest spread that one's going to be chosen as your split dimension.

[01:12:43] So you're going to choose that dimension and then you're going to split it right in the middle. Now, when I say in the middle, I don't mean like in the middle of the extremes, but you're going to split it such that half the points go on the left and half the points go on the right. And so while you're computing the spread and you can also be, you know, finding that middle, finding that median point.

[01:13:06] So if you imagine the root node, the root node is going to look at your entire dataset, find which dimension has the largest spread. And then slice that dimension, such that half the points go to one child and half the points go to the other child. And then all that root, no needs to keep track of is which dimension it was split on.

[01:13:25] And where in that dimension, the split was. Now, then each of the children will do the same thing. And so you'll keep doing this until you get to a node where there aren't that many children. At that point, you'll say, well, there's no point in me splitting again. I'm just going to have like, just a list of points at this, at that level.

[01:13:47] And so k-d trees are super, super important, because, there's a really, really cool trick you could do at them. In machine learning. You have this challenge, right, where let's say you're Amazon, right. And someone types in batteries. And so you need to return back a list of items that you think that person would be interested in. Right?

[01:14:14] But the problem is Amazon has like a billion items, right. Or maybe even if you take it even workstream, let's say someone just goes to amazon.com. They don't even put a search. So you need to show them some items you think they would like. And there's just so many items, probably a billion skews in Amazon's catalog. Right?

[01:14:34] So you can do this trick. Let's say you had a vector, a vector, just like a set of numbers. Let's say you had a set of numbers to describe a person. Right. And so, you know, that, that might be sort of like some way of capturing, like their history and the things you think they like, and you were to sort of what's called embed that, or create just like a single point for that person.

[01:15:00] And then you also do this for all your different products. So for all your different products, you have kind of like, a point or a vector, a list of numbers, or a point in a space somewhere describing that product. So now what you need to do something called nearest neighbors. So you need to say like, what are the nearest products, the nearest points, product points to this person point that I've created.

[01:15:27] And it turns out if you use a k-d tree, you can do that very, very quickly. Things like nearest neighbor search can happen extremely quickly in k-d tree, because for example, look at that first split, that first split might be like so far away from where the person point is, that you could say anything on the other side of that split.

[01:15:48] There's no way that any of those points are my nearest neighbor. And so that's, right away, that's half the data you don't have to look at. Right. And so you can kind of take that, that sort of intuition. Now basically. Yeah, you can kind of follow the k-d tree down to the final part of the k-d tree that has your, your person in it, your person pointed it and look at the products there.

[01:16:15] And then maybe look at like some of the products, you know, higher up in the tree, but you definitely don't have to look at the entire tree. You can ignore 99% of the tree. And so this is how Amazon does, at the end of the day, this is how they can show you stuff so quickly, even though they have so many items.

[01:16:33] And so there's a lot of work that goes into like, the embeddings and how you create the tree and everything, but extensively, you know, they just have a giant k-d tree that they've implemented. And when you come to Amazon, they find the nearest things to you in that tree. That's how it works.

[01:16:50] Patrick Wheeler: So to highlight one difference and then talk about one final thing. I think when Jason is describing like this nearest neighbor search. On multidimensions, which, which we sort of called these spatial trees, because that tends to be one way of thinking about it. But when we're talking up front about b-trees and binary trees, we're talking about a single number line, basically, where all of your elements live on.

[01:17:13] And when we talk about multi-dimensional, it's having at least two or more dimensions, and the problem there becomes there, isn't direct way of viewing. Like I'm just going to go in dimension one and then dimension two, like that turns out to be really inefficient. So both k-d, Jason and things I'm going to talk about, and some others, try to divvy up the space in a way that moves back and forth between the dimensions. And as Jason was saying, using the spread, you might divide on the X line, the X line, but then you'll go by the Y line. Right. And you're sort of intermixing the two dimensions. and trying to sort of interleave so that you can get to your answer a little bit faster and when you're traversing, the other interesting thing is you may end up having to go through multiple branches in order to find the nearest neighbor.

[01:18:01] So once you go down one branch, you know how far away the split was from you, and if your answer ends up being further away than that split was you actually have to go visit the stuff on the other side of that split. And that's true as well for a variety of these facial trees and doing that nearest neighbor search.

[01:18:21] And the other thing that both his k-d tree explanation and my, oh man, I say to this out of order, think I'm about to talk about also support, which is very similar, is for clearing ranges. Or if you think about in 2d, it would be rectangles or boxes. Right? So if you drew a rectangle and said, I want everything inside of this rectangle, they need to be efficient at doing that.

[01:18:42] And it's a little hard to describe over audio, but I mean, both of them are well-suited to being able to do that. So both Jason talked about splitting the data on, you know, one of the axes at each level. So instead of looking at your data and sort of splitting based on what the data says, instead, if you come up with predefined splits based on your space, you come up with a different, spacial tree called a quadtree for two dimensions or an octree for three dimensions. I don't know what it would be for four dimensions. I've never heard of someone doing that, but maybe you could.

[01:19:16] And so if you imagine in two dimensions having, let's just say a square, right. And you divide that square once in the middle, up and down and once in the middle left and right. then you end up with four quadrants of that space.

[01:19:30] And now you see why it's called a quadtree. So the root node would be the base sort of square. Then the first set of children, there would be four and one would be the upper left. One would be the upper, right. I'm going to be the bottom left and one would be the bottom. Right. And what that does is that sort of dimension mixing, I was talking about you get it, right?

[01:19:49] So as you go, you know, child zero one, two, three, you're actually traversing, both dimensions sort of intermixed, but the quadtree, what it does is say, if I have a set of points scattered around in my square, I'm going to keep subdividing my space until I get, you could say just one theme in each square. So the disadvantage is that as you're cutting down and down and down, if you have two points really close to each other, you might need a lot of splits before you get to the split that separates the two.

[01:20:24] And so you could have a lot of depth, right. But, in traversing, it actually ends up working really similar to how the k-d tree does. The advantage of a quadtree is that I can figure out where in the tree it goes from the start. So if I know the level, I want to go to, like, let's say level five split, I can compute in closed form, which traversal of the tree I would need to place that element in the tree there.

[01:20:50] The other nice thing is that if you have dynamic data where your data is moving around, so imagine like someone shoots a laser beam out of your spaceship and your game, and you have your world game split up in a quadtree or fits in three dimensions, an octree, which is the same thing. But with eight children, if you imagine that laser bolt moving through space and needing to do these nearest neighbor queries, which is what you would want to do, if you wanted to see, like, if I hit something in my current box, then this traversal you can figure out and sort of a more direct, closed form on computation and do the management and a sort of much cheaper way, rather than reshuffling and potentially needing to re split, like you would need to, for k-d to your other kinds of spacial trees that would be used.

[01:21:31] So they're similar in actually the way you use it. And once you start looking at algorithms between them, like once you figured it out once. It kind of ends up being pretty similar for all of them and how to do these range searches and nearest neighbos searches.

[01:21:44] I find that these quadtrees and octrees are used a lot in games for, for dynamic data and the quadtree, k-d tree, there's also one more this worth mentioning, I guess, which is like an r-tree, which is taking a group of data and drawing a rectangle around it, and then building a tree of rectangles over multiple rectangles. And I won't go into it more than that.

[01:22:06] And you'll see that also used a lot in sort of mapping data, geographical or geographic information systems, GIS systems. We'll use these a lot in databases and stuff. Also, I think k-d trees can also be used in video games. I've seen them used for like splitting up a level and understanding, which polygons you want to draw or not because the level itself, like the environment tends to be static.

[01:22:31] And so you can, a priori before you're like, when you're making your level, you can do the split, and have it stored so that when you're trying to figure out which polygons to render you just traverse this pre-made tree rather than having to build it at runtime.

[01:22:44] Jason Gauci: Yeah, totally. Yeah. I think you really hit the nail on the head. I think k-d trees and r-trees, the structure of the tree is dependent on the data. So, you know, as Patrick said, if, if your data is like really wide, you might have a lot of, a lot of vertical splits before you start seeing some horizontal splits. If data is really narrow, it's going to be the opposite.

[01:23:08] And yeah. In the case of the r-tree, you know, if there's a part of the space, that's very dense. I mean, imagine building an r-tree of the US, right? You're going to have like a ton of rectangles around like New York City, San Francisco, Los Angeles. Right? 'Cause I mean, I imagine you're building an r-tree on like over like businesses or addresses in the US, right?

[01:23:28] There's just a lot more addresses in a tiny space in New York city. Right? And so the structure of the tree will, you know, even all the way up to the decisions made at the very top, will be influenced heavily by the distribution of the data, versus like in the case of a quadtree, you know, now there might be nodes that exist or don't exist because of the data.

[01:23:54] But the structure, like the way that the splits are done is totally immutable and it has nothing to do with, with the data, right? And so, you know, that's sort of like a double-edged sword, right on one hand, If you're not splitting in a, in a informed way, then you're not going to be very efficient. And so if you're doing something just once, like if you're creating a tree off some data that's not changing and then using it a lot of times, like that's what Amazon is doing.

[01:24:23] Amazon will create this giant tree. and that might take a lot of time, but then they're going to swap it out with the old tree, and then they're going to use that new tree, you know, billions and billions of times. And so they know they can afford to have this sort of frozen set, right? And so, and so they'll use like a k-d tree or an r-tree or something like that.

[01:24:48] But for games, you know, the content is moving all the time. I mean, there's, there's there's, as Patrick said, like if you have, people walking around on a map, shooting laser beams and all these things, you know, then, then you would, you can't have the structure of the tree dependent on these things that are constantly moving around. And so for games, they'll use these octrees and quadtrees.

[01:25:09] And my guess is, and I think you alluded to this, Patrick, is your games will probably need both, because the level doesn't move, unless you're playing like Minecraft or something, but the level doesn't, geometry doesn't change. And so that would be much better served by something like a k-d tree or r-tree.

[01:25:26] And, and there's actually more like exotic trees for certain domains. There's like a BSP tree. There's a, you know, vantage point trees. And so they'll use something like that. And, but then for actually storing all of the dynamic content, they'll use something like an octree.

[01:25:44] Patrick Wheeler: That was a lot of fun. Yeah, totally.

[01:25:46] Jason Gauci: I totally got the geek out on trees. If we missed any trees, let us know. Or if we...

[01:25:52] Pine trees. Oak trees.

[01:25:53] Yeah, that's right. Birch. Yeah. Minecraft taught me a lot about trees. Been playing, playing that a lot with the kids. And I learned that Birch is a thing. So, I don't quite know, like the order, the big O-notation of a Birch. I'll have to figure that one out.

[01:26:11] But thank you so much, everyone for, all of your support. let us know what you think about the duo episodes. We were bringing them back. We still have, a lot of really awesome interviews lined up. So, you know, looking forward to that. But we'll be kind of intermixing some of these, you know, duo episodes in there.

[01:26:32] And definitely give us some feedback. We really appreciate all the feedback you have been giving and just keep it up. Let us know what you think about the show. We definitely look at all of them. we've gotten a lot of our show ideas from listeners. This was one that we, we really wanted to do ourselves, but, but we've taken a lot of really great show topics from listeners and that's all because of you and, you know, continuing support and feedback.

[01:26:54] So we appreciate it.

[01:26:56] Patrick Wheeler: Yeah. Thanks everyone.

[01:26:57] Jason Gauci: See you later.

[01:26:59] Music by Eric Barndollar

[01:27:02] Programming Throwdown is distributed under Creative Commons, Attribution ShareAlike 2.0 license. You're free to share, copy, distribute, transmit the work, to remix, and adapt the work, but you must provide attribution to Patrick and I, and sharealike in kind.